萧芸斓是Z国的公主，平时的一大爱好是采花。 今天天气晴朗，阳光明媚，公主清晨便去了皇宫中新建的花园采花。花园足够大，容纳了n朵花，花有c种颜色（用整数1-c表示），且花是排成一排的，以便于公主采花。公主每次采花后会统计采到的花的颜色数，颜色数越多她会越高兴！同时，她有一癖好，她不允许最后自己采到的花中，某一颜色的花只有一朵。为此，公主每采一朵花，要么此前已采到此颜色的花，要么有相当正确的直觉告诉她，她必能再次采到此颜色的花。由于时间关系，公主只能走过花园连续的一段进行采花，便让女仆福涵洁安排行程。福涵洁综合各种因素拟定了m个行程，然后一一向你询问公主能采到多少朵花（她知道你是编程高手，定能快速给出答案！），最后会选择令公主最高兴的行程（为了拿到更多奖金！）。
感觉这道题挺好，一开始写了莫队，蒟蒻自以为可以过，结果却无情得T了。 之后膜了一下star_feel大佬后，发现这道题要用一种新思路。 每个位置用一个next数组记录等于它这个值的下一个离它最近的位置。 用树状数组一开始让所有颜色出现第二次的位置的值为1，其它为0，因为其它的位置没有贡献。 然后给每个询问的左端点进行排序，然后让l一开始等于1，之后便向询问的左端点靠拢，让被忽略的点x的next的值便为0，因为它在当前区间出现的颜色为第一次的，让next[next[x]]的值为1，因为它在当前区间就为第二次了。最后答案就为1～r的值的和减去1～(l-1)的值的和，之后再顺序输出就可以了。
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<cstdlib> using namespace std; struct node { int l,r,id; }q[2000010]; bool cmp(node a,node b) { if(a.l>b.l)return false; if(a.l<b.l)return true; return 0; } int n,m,c; int a[2000010],s[2000010],v[2000010]; int next[2000010],b[2000010],ss[2000010]; int lowbit(int x){return x&-x;} void add(int x,int w) { while(x<=n) { s[x]+=w; x+=lowbit(x); } } int getsum(int x) { int ans=0; while(x>=1) { ans+=s[x]; x-=lowbit(x); } return ans; } int main() { scanf("%d%d%d",&n,&c,&m); for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int i=n;i>=1;i--) { next[i]=b[a[i]]; b[a[i]]=i; } for(int i=1;i<=m;i++) { scanf("%d%d",&q[i].l,&q[i].r); q[i].id=i; } sort(q+1,q+m+1,cmp); for(int i=1;i<=n;i++) { if(v[a[i]]==1)add(i,1); v[a[i]]++; } int l=1; for(int i=1;i<=m;i++) { while(l<q[i].l) { if(next[l])add(next[l],-1); if(next[next[l]])add(next[next[l]],1); l++; } ss[q[i].id]=getsum(q[i].r)-getsum(q[i].l-1); } for(int i=1;i<=m;i++)printf("%d\n",ss[i]); return 0; }