记录编号	130782	评测结果	AAAAAAAAAA
题目名称	[SDOI 2009] HH的项链	最终得分	100
用户昵称	Ezoi_XY	是否通过	通过
代码语言	C++	运行时间	0.312 s
提交时间	2014-10-23 09:36:48	内存使用	11.35 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct query{
	int l, r, o;
	bool operator <(query q) const{
		return r < q.r;
	}
} q[200011];
int a[50011], l[1000011], n, m, b[50011], ans[200011];
char ibuf[2800011], *ipt(ibuf), obuf[1200011], *opt(obuf), tmp[11], *tp(tmp);
inline void gi(int &x){
	x = 0;
	while (*ipt < '0' || *ipt > '9') ++ipt;
	while (*ipt >= '0' && *ipt <= '9') x = x * 10 + *ipt++ - '0';
}
inline void pi(int x){
	for (++tp; x; ++tp, x /= 10) *tp = x % 10 + '0';
	for (--tp; *tp; --tp, ++opt) *opt = *tp;
	*opt = '\n'; ++opt;
}
inline void add(int p, int x){
	for (; p <= n; p += p & -p) b[p] += x;
}
inline int sum(int p){
	int s(0);
	for (; p; p -= p & -p) s += b[p];
	return s;
}
int main(){
	freopen("diff.in", "r", stdin);
	freopen("diff.out", "w", stdout);
	fread(ibuf, 1, 2800011, stdin);
	int i, j;
	gi(n);
	for (i = 1; i <= n; ++i) gi(a[i]);
	gi(m);
	for (i = 0; i < m; ++i) gi(q[i].l), gi(q[i].r), q[i].o = i;
	sort(q, q + m);
	for (i = 1, j = 0; i <= n && j < m; ++i){
		add(l[a[i]] + 1, 1); add(i + 1, -1);
		l[a[i]] = i;
		while (j < m && q[j].r == i) ans[q[j].o] = sum(q[j].l), ++j;
	}
	for (i = 0; i < m; ++i) pi(ans[i]);
	fwrite(obuf, 1, opt - obuf, stdout);
	return 0;
}