Rockdu's Blog

题目背景

无

题目描述

HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH 不断地收集新的贝壳，因此，他的项链变得越来越长。有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答……因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。

输入输出格式

输入格式：

第一行：一个整数N，表示项链的长度。

第二行：N 个整数，表示依次表示项链中贝壳的编号（编号为0 到1000000 之间的整数）。

第三行：一个整数M，表示HH 询问的个数。

接下来M 行：每行两个整数，L 和R（1 ≤ L ≤ R ≤ N），表示询问的区间。

输出格式：

M 行，每行一个整数，依次表示询问对应的答案。

输入输出样例

6
1 2 3 4 3 5
3
1 2
3 5
2 6

2
2
4

说明

数据范围：

对于100%的数据，N <= 50000，M <= 200000。

因为这道题不涉及修改，我们可以考虑把操作离线。考虑到一段区间内如果我们维护每一个数最后出现的下标，那么我们只用权值树状数组维护每一个下标有最后出现的数的个数，那么查询区间内的数的个数就是查询答案。这样我们把查询按R排好序，查询的时候我们只用统计L,R下标内的数的个数，并且边查询边往后加入新的贝壳就可以了。

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 1e6 + 10;
const int maxm = 2e5 + 10;
int n, m, a;
struct q {
	int l, r, org;
	bool operator <(const q &b) const {return r == b.r ? l < b.l : r < b.r;}
}qs[maxm];
int num[maxm], rank[maxn], now, ans[maxn];
namespace BIT {
	#define lowbit(x) ((x) & -(x))
	int tree[maxn], N = maxn;
	void add(int p, int x) {
		while(p <= N) 
			tree[p] += x, p += lowbit(p);
	}
	int query(int p) {
		int ans = 0;
		while(p) ans += tree[p], p -= lowbit(p);
		return ans;
	}
}

int main() {
	scanf("%d", &n);
	for(register int i = 1; i <= n; ++i) {
		scanf("%d", &num[i]);
		//if(rank[num[i]]) BIT::add(rank[num[i]], -1);
		//rank[num[i]] = i, BIT::add(i, 1);
	}
	scanf("%d", &m);
	for(register int i = 1; i <= m; ++i) 
		scanf("%d%d", &qs[i].l, &qs[i].r), qs[i].org = i;
	sort(qs + 1, qs + m + 1);
	for(register int i = 1; i <= m; ++i) {
		int r = qs[i].r, l = qs[i].l;
		while(++now <= r) {
			if(rank[num[now]]) 	BIT::add(rank[num[now]], -1);
			BIT::add(now, 1), rank[num[now]] = now;
		}
		--now, ans[qs[i].org] = BIT::query(r) - BIT::query(l - 1);
		//printf("%d : %d %d : %d\n", l, BIT::query(l), r, BIT::query(r));
	}
	for(register int i = 1; i <= m; ++i) printf("%d\n", ans[i]);
	return 0;
}