Description:

Given a sequence of integers a 1 , a 2 , . . . , a n a_1, a_2, ..., a_n a1​,a2​,...,an​ and q q q pairs of integers ( l 1 , r 1 ) , ( l 2 , r 2 ) , . . . , ( l q , r q ) , (l_1, r_1), (l_2, r_2), ..., (l_q, r_q), (l1​,r1​),(l2​,r2​),...,(lq​,rq​), find count ( l 1 , r 1 ) (l_1, r_1) (l1​,r1​), count ( l 2 , r 2 ) (l_2, r_2) (l2​,r2​), …, count ( l q , r q ) (l_q, r_q) (lq​,rq​) where count ( i , j ) (i, j) (i,j) is the number of different integers among a 1 , a 2 , . . . , a i , a j , a j + 1 , . . . , a n . a_1, a_2, ..., a_i, a_j, a_{j + 1}, ..., a_n. a1​,a2​,...,ai​,aj​,aj+1​,...,an​.

Input:

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 n n and q q q.
The second line contains n n n integers a 1 , a 2 , . . . , a n a_1, a_2, ..., a_n a1​,a2​,...,an​.
The i − t h i-th i−th of the following q q q lines contains two integers l i l_i li​ and r i r_i ri​.

Output:

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

Sample Input:

3 2
1 2 1
1 2
1 3
4 1
1 2 3 4
1 3

Sample Output:

2
1
3

题目链接

使用离线树状数组做法，先读入询问数据，之后按照右端点升序处理，最后输出结果。

在数列中从左至右遍历，当遍历到 i i i位置时若 a [ i ] a[i] a[i]的最后一次出现位置是 i i i位置，因为询问是按照右端点升序处理，所以在处理下一次询问中只用根据 f i r s t [ a [ i ] ] first[a[i]] first[a[i]]也就是 a [ i ] a[i] a[i]第一次出现的位置和询问左端点的位置关系判断 a [ i ] a[i] a[i]是否在 1 → l 1\rightarrow l 1→l和 r → n r \rightarrow n r→n之间，在遍历时不断维护树状数组count。

AC代码:

#pragma comment(linker, "/STACK:102400000,102400000")
#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
#define lowbit(x) (x&(-x))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5+5;
const int mod = 1e9+7;
const double eps = 1e-8;
const double pi = asin(1.0)*2;
const double e = 2.718281828459;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}

// 询问结构体
struct query {
	int l, r, id;
	query(int _l = 0, int _r = 0, int _id = 0): l(_l), r(_r), id(_id) {}
};

int main(int argc, char *argv[]) {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int n, q;
	while (~scanf("%d%d", &n, &q)) {
		vector<int> a(n + 1), first(n + 1, -1), last(n + 1);
		// 统计不同数字个数
		int total = 0;
		for (int i = 1; i <= n; ++i) {
			read(a[i]);
			// 覆盖记录数字最后一次出现位置
			last[a[i]] = i;
			// 记录数字第一次出现的位置并将数字个数+1
			if (first[a[i]] == -1) {
				++total;
				first[a[i]] = i;
			}
		}
		// 读入存储每个询问
		vector<query> Query;
		for (int i = 0, l, r; i < q; ++i) {
			read(l); read(r);
			Query.pb(query {l, r, i});
		}
		// 将询问按照右端点升序排序
		sort(Query.begin(), Query.end(), [&] (const query &a, const query &b) {
			return a.r < b.r;
		});
		vector<int> ans(q), count(n + 1, 0);
		// 从左至右遍历每个位置
		for (int i = 1, k = 0; i <= n; ++i) {
			// 若还有未处理的询问并且正在遍历此询问右端点
			while (k < q && Query[k].r == i) {
				// 先把此询问结果赋值为所有范围内不同数字个数
				ans[Query[k].id] = total;
				//　从此询问左端点开始遍历至最右减去在左端点至右端点不统计的数字个数
				for (int j = Query[k].l; j <= n; j += lowbit(j)) {
					ans[Query[k].id] -= count[j];
				}
				// 处理询问数+1
				++k;
			}
            // 若查询处理完毕则跳出
            if (k >= q) {
                break;
            }
			// 若遍历到的位置上的数字为最后一次出现，则把它第一次出现的位置之前count+1
			if (last[a[i]] == i) {
				for (int j = first[a[i]] - 1; j > 0; j -= lowbit(j)) {
					count[j]++;
				}
			}
		}
		// 输出结果
		for (auto i : ans) {
			printf("%d\n", i);
		}
	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("gedit out.txt");
#endif
    return 0;
}