记录编号	367312	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016]采花	最终得分	100
用户昵称	‎MistyEye	是否通过	通过
代码语言	C++	运行时间	2.278 s
提交时间	2017-01-29 22:04:48	内存使用	149.09 MiB

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 200005;
struct Node {
	int sum;
	Node *lc, *rc;
};
Node p[maxn<<6], *root[maxn], *p_;
int bef[maxn], last[maxn], w, d, le, ri;
void build(int l, int r, Node *s0, Node *&s) {
	s = ++p_; *s = *s0; s->sum += d;
	if(l==r) return;
	int mid = (l+r)>>1;
	if(w<=mid) build(l, mid, s0->lc, s->lc);
	else build(mid+1, r, s0->rc, s->rc);
}
int query(int l, int r, Node *s0, Node *s) {
	if(le<=l && r<=ri) return s->sum-s0->sum;
	int mid = (l+r)>>1, ans = 0;
	if(le<=mid) ans += query(l, mid, s0->lc, s->lc);
	if(ri> mid) ans += query(mid+1, r, s0->rc, s->rc);
	return ans;
}
int main() {
	freopen("flower++.in", "r", stdin); 
	freopen("flower++.out", "w", stdout);
	int N, C, Q; scanf("%d%d%d", &N, &C, &Q);
	root[0] = p_ = p; p->lc = p->rc = p;
	for(int i=1, a; i<=N; ++i) {
		scanf("%d", &a);
		Node *t = root[i-1];
		w = bef[a]; d = 1; bef[a] = last[a];
		build(0, N, root[i-1], t);
		w = last[a]; d = -1; last[a] = i;
		build(0, N, t, root[i]);
	} // 这样显然没有直接模拟离线的操作简单
	int x, y, ans = 0; 
	for(int i=1; i<=Q; ++i) {
		scanf("%d%d", &x, &y);
		x ^= ans, y ^= ans;
		le = 0,	ri = x-1; 
		ans = query(0, N, root[x-1], root[y]);
		printf("%d\n", ans);
	}
	getchar(), getchar();
	return 0;
}