这种统计种类(颜色)的问题总是很恶心;%%%REfun
首先对于所有询问的区间,按照右端点排序;
我们动态维护一棵线段树;从左到右枚举每个点,枚举到一个点: 1 、我们就把他的位置对应的线段树里加上值: 2、同时我们记录上一个同一个颜色的位置,把这个位置在线段树中删除;
我们判断,当前枚举到的点是否是一个询问区间的右端点(这就是我们为什么按照右端点排序的原因),区间查询即可!
思路非常巧妙啊!学习了!%refun
#include#include #include using namespace std; const int maxn=1e6; const int inf=1e9; int n,m,a[maxn],tot,ans[maxn],last[maxn];//last记录上一个相同元素出现的位置 struct QQ{ int x,y,id; }qq[maxn]; bool cmp(QQ x,QQ y) {if (x.y==y.y) return x.x >1; if (x<=mid) change(x,C,l,mid,rt<<1); else change(x,C,mid+1,r,rt<<1|1); pushup(rt); } int ques(int L,int R,int l,int r,int rt) { if (L<=l && r<=R) return sum[rt]; int mid=(l+r)>>1; int ans=0; if (L<=mid) ans+=ques(L,R,l,mid,rt<<1); if (R>mid) ans+=ques(L,R,mid+1,r,rt<<1|1); return ans; } int main() { scanf("%d",&n); for (int i=1; i<=n; i++) scanf("%d",&a[i]); scanf("%d",&m); for (int i=1; i<=m; i++) { qq[i].id=i; scanf("%d%d",&qq[i].x,&qq[i].y); } sort(qq+1,qq+1+m,cmp); tot=1; for (int i=1; i<=n; i++) { change(i,1,1,n,1); if (last[a[i]]) change(last[a[i]],0,1,n,1); last[a[i]]=i; while (qq[tot].y==i) { ans[qq[tot].id]=ques(qq[tot].x,qq[tot].y,1,n,1); tot++; } } for (int i=1; i<=m; i++) printf("%d\n",ans[i]); return 0; }
这种动态维护线段树并维护的思想;