求区间内不同数字的个数(树状数组)

题干

给一个序列，让你求[l, r]中不同数字的个数

输入

输入一个n，随后是含有n个数字的序列

输入一个q，随后是两个整数，代表查询区间

输出

q个查询的结果

样例

Input
5
1 1 2 1 3
3
1 5
2 4
3 5

Output
3
2
3 

思路

用一个树状数组记录序列前i个数字中，不同数字的个数。

从一个查询区间的左侧开始扫描：

1. 数字首次出现时，当前位置加一，且用map记录下当前数字出现的位置
2. 数字非首次出现时，当前位置加一，但是上次出现的位置要减一

一个查询区间结束后，getsum(r) - getsum(l - 1)即为答案。

仔细思考上述过程，当执行第二种情况时，会破坏之前的结果，因此整个序列扫描的过程，必须保证一次完成。

因此要注意：

1. 按照查询区间的右端点值进行排序（当前的会破坏前面的结果）
2. 保证整个序列中的元素仅扫描一次，即代码中的`pre = query[i].r + 1;`而不是`pre = query[i + 1].l;`

代码

#include <stdio.h>
#include <string>
#include <stdlib.h>
#include <iostream>
#include <vector>
#include <string.h>
#include <algorithm>
#include <map>
using namespace std;
const int maxn = 10000;
int n = 0, q = 0;

struct Query{
	int id, l, r;
	bool operator< (Query a) const{
		return r < a.r;
	}
}query[maxn];



int v[maxn], sum[maxn], ans[maxn];

int lowbit(int x){
	return x & (-x);
}

void change(int i, int a){
	while(i <= n){
		sum[i] += a;
		i += lowbit(i);
	}
}

int getsum(int i){
	int sum_t = 0;
	while(i > 0){
		sum_t += sum[i];
		i -= lowbit(i);
	}
	return sum_t;
}

int main() {
	
	while(~scanf("%d", &n)){
		memset(v, 0, sizeof(v));
		memset(sum, 0, sizeof(sum));
		memset(ans, 0, sizeof(ans));
		
		int t = 0;
		for(int i = 1; i <= n; i++){
			scanf("%d", &v[i]);
		}
		scanf("%d", &q);
		for(int i = 1; i <= q; i++){
			scanf("%d%d", &query[i].l, &query[i].r);
			query[i].id = i;
		}
		sort(query + 1, query + q + 1);
		
		int pre = 1;
		map<int, int> mymap;
		for(int i = 1; i <= q; i++){
			for(int j = pre; j <= query[i].r; j++){
				//已存在 
				if(mymap[v[j]]){
					change(mymap[v[j]], -1);
				}
				mymap[v[j]] = j;
				change(j, 1);
			}
			pre = query[i].r + 1;
			ans[query[i].id] = getsum(query[i].r) - getsum(query[i].l - 1);
		}
		
		for(int i = 1; i <= q; i++){
			cout << ans[i] << endl;
		}
	}
	return 0;
}