记录编号	280152	评测结果	AAAAAAAAAA
题目名称	[SDOI 2009] HH的项链	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	1.407 s
提交时间	2016-07-10 07:14:50	内存使用	5.88 MiB

#include<cstdio>
#include<cctype>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std; 
int read(){
    int x;char ch;
    while(ch=getchar(),!isdigit(ch));
    x=ch-'0';
    while(ch=getchar(),isdigit(ch))x=x*10+ch-'0';
    return x;
}
const int maxn=50005,maxm=200005,maxc=1000005;
int S;
int a[maxn];
struct query{
    int l,r,num,ans;
}Q[maxm];
bool cmp(const query &a,const query &b){//this is a smart compare function 
    return ((a.l-1)/S==(b.l-1)/S)?a.r<b.r:a.l<b.l;
}
bool cmp2(const query &a,const query &b){
    return a.num<b.num;
}
int cnt[maxc];
int main(){
	freopen("diff.in","r",stdin);
	freopen("diff.out","w",stdout);
    int n=read();
    for(int i=1;i<=n;++i)a[i]=read();
    int m=read();
    for(int i=1;i<=m;++i){
        Q[i].l=read();Q[i].r=read();
        Q[i].num=i;
    }
    S=sqrt(n+0.5);
    sort(Q+1,Q+m+1,cmp);
    for(int j=Q[1].l;j<=Q[1].r;++j){
    	if(!cnt[a[j]])Q[1].ans++;
    	cnt[a[j]]++;
    }
	for(int i=2;i<=m;++i){
        Q[i].ans=Q[i-1].ans;
        if(Q[i-1].r<Q[i].r){
			for(int j=Q[i-1].r+1;j<=Q[i].r;++j){
            	if(!cnt[a[j]])Q[i].ans++;
           	 	cnt[a[j]]++;
        	}
		}
		else if(Q[i-1].r>Q[i].r)
		{	for(int j=Q[i-1].r;j>Q[i].r;--j){
				cnt[a[j]]--;
				if(!cnt[a[j]])Q[i].ans--;
			}
		}
        if(Q[i].l<Q[i-1].l){
            for(int j=Q[i].l;j<Q[i-1].l;++j){
                if(!cnt[a[j]])Q[i].ans++;
                cnt[a[j]]++;
            }
        }else if(Q[i].l>Q[i-1].l){
            for(int j=Q[i-1].l;j<Q[i].l;++j){
                cnt[a[j]]--;
                if(!cnt[a[j]])Q[i].ans--;
            }
        }
    }
    sort(Q+1,Q+m+1,cmp2);
    for(int i=1;i<=m;++i)printf("%d\n",Q[i].ans);
    fclose(stdin);fclose(stdout);
    return 0;
}/*
10
1 3 2 4 3 5 4 6 5 7
8
1 5
6 10
1 9
3 7
2 5
1 2
3 5
7 7
4
4
6
4
3
2
3
4
*/