bzoj1878 [SDOI2009]HH的项链

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<string>
 5 #include<cstring>
 6 #include<cmath>
 7 #include<algorithm>
 8 #include<ctime>
 9 #include<queue>
10 #include<stack>
11 #include<map>
12 #include<set>
13 #define lowbit(x) x&-x;
14 using namespace std;
15 int getint()
16 {
17     int ret=0;
18     char ch=getchar();
19     while(ch<‘0‘||ch>‘9‘)ch=getchar();
20     while(ch>=‘0‘&&ch<=‘9‘)ret*=10,ret+=ch-‘0‘,ch=getchar();
21     return ret;
22 }
23 int n,m,Max;
24 int a[50050],next[50050],sum[50050],p[1000050];
25 struct wen
26 {
27     int l,r,id,ans;
28     bool operator < (const wen &a)const
29     {
30         return id<a.id;
31     }
32 }q[200050];
33 bool com(const wen &a,const wen &b)
34 {
35     return a.l==b.l?a.r<b.r:a.l<b.l;
36 }
37 void add(int i,int x)
38 {
39     while(i<=n)sum[i]+=x,i+=lowbit(i);
40 }
41 int query(int i)
42 {
43     int ret=0;
44     while(i)ret+=sum[i],i-=lowbit(i);
45     return ret;
46 }
47 int main()
48 {
49     n=getint();
50     for(int i=1;i<=n;i++)
51     {
52         a[i]=getint();
53         Max=max(Max,a[i]);
54     }
55     for(int i=n;i>=1;i--)
56         next[i]=p[a[i]],p[a[i]]=i;
57     for(int i=1;i<=Max;i++)if(p[i])add(p[i],1);
58     m=getint();
59     for(int i=1;i<=m;i++)
60     {
61         q[i].l=getint(),q[i].r=getint();
62         q[i].id=i;
63     }
64     sort(q+1,q+m+1,com);
65     int l=1;
66     for(int i=1;i<=m;i++)
67     {
68         while(l<q[i].l)
69             if(next[l])add(next[l++],1);
70             else l++;
71         q[i].ans=query(q[i].r)-query(q[i].l-1);
72     }
73     sort(q+1,q+m+1);
74     for(int i=1;i<=m;i++)
75         printf("%d\n",q[i].ans);
76     return 0;
77 }