首页 > 试题广场 >

Different Integers

[编程题]Different Integers

时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 512M，其他语言1024M
算法知识视频讲解

Given a sequence of integers a₁, a₂, ..., a_n and q pairs of integers (l₁, r₁), (l₂, r₂), ..., (l_q, r_q), find count(l₁, r₁), count(l₂, r₂), ..., count(l_q, r_q) where count(i, j) is the number of different integers among a₁, a₂, ..., a_i, a_j, a_{j + 1}, ..., a_n.

输入描述:

The input consists of several test cases and is terminated by end-of-file.
The first line of each test cases contains two integers n and q.
The second line contains n integers a₁, a₂, ..., a_n.
The i-th of the following q lines contains two integers l_i and r_i.

输出描述:

For each test case, print q integers which denote the result.

示例1

输入

输出

2
1
3

备注:

* 1 ≤ n, q ≤ 10⁵
* 1 ≤ a_i ≤ n
* 1 ≤ l_i, r_i ≤ n
* The number of test cases does not exceed 10.

算法知识视频讲解

回归梦想

发表于 2020-11-11 21:13:56

题目描述题解：个人感觉这个题真不错。。。emmm。。为什么这么说，这个题有多种做法：1.树状数组2.莫队算法3.主席树4.线段树想讲讲我的做题过程，再讲正解做题过程第一反应就是树状数组我想的很简单，只将第一次出现的数字插入到树状数组中，最后记录[r,n]和[1,l]的答案ll w=get 展开全文

19-大数据一班-杨文冠

发表于 2021-07-29 17:25:19

题意：给出个数，求 ,这两个区间不同数的个数思路：其实只要把区间扩大一倍，就是求这个区间了定义数组中第一次出现的数的后缀为，第次出现的数的后缀为该数第次出先时的下标。比如：原数组为，扩大一倍后为，每个数对应的后缀为。如果某个数出现多次，而我们只算最右边的那个，我们会发现最右边的那个数的后缀展开全文

已经死了

发表于 2023-07-13 22:17:42

思路离线查询，树状数组维护查询按右端点r排序，遍历查询，当一个数字全出现了，那就把这个数字第一次出现的下标单点+1 查询[l+1,r-1]的区间和，用总的去减就可以了 import sys,random,bisect from collections import deque,defaultdic 展开全文