题意

有一个长度为n的序列，每次询问[l,r]中有多少种颜色出现了两次以上。 n,q<=1000000

分析

一眼莫队的说。。。但看到数据范围就怂了。 假设现在询问的区间是[l,r]，那么我们可以把第二次出现的数的权值看做1，其余看做0，就可以把问题变成求区间和了。那么只要把询问离线一下，然后从后往前做，用一棵树状数组来资辞单点修改区间查询即可。

代码

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; const int N=1000005; int n,m,c[N],nx[N],ls[N],last[N],a[N]; struct edge{int r,next,ans;}e[N]; int read() { int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } void ins(int x,int y) { while (x<=n) { c[x]+=y; x+=x&(-x); } } int find(int x) { int ans=0; while (x) { ans+=c[x]; x-=x&(-x); } return ans; } int main() { n=read();int c=read();m=read(); for (int i=1;i<=n;i++) a[i]=read(); for (int i=n;i>=1;i--) nx[i]=ls[a[i]],ls[a[i]]=i; for (int i=1;i<=m;i++) { int l=read(),r=read(); e[i].r=r;e[i].next=last[l];last[l]=i; } for (int i=n;i>=1;i--) { if (nx[i]) { if (!nx[nx[i]]) ins(nx[i],1); else ins(nx[nx[i]],-1),ins(nx[i],1); } for (int j=last[i];j;j=e[j].next) e[j].ans=find(e[j].r); } for (int i=1;i<=m;i++) printf("%d\n",e[i].ans); return 0; }