题目链接
题目大意：询问[l,r]中不同元素个数
题解：树状数组（比较神），或者莫队
我的收获：套路&&莫队第一题达成
树状数组
以每个数字第一次在区间中出现的点代表所有的点。 记录每个位置i的数字的前一个相同数字出现的位置pre[i]，没有前一个相同的pre[i]为0
把询问转化一下，[l,r]中出现一次等价于pre[]在[1,l-1]中 添加一个元素i后，将pre[i]+1,i-1，然后求个a[i].l的前缀和
每次添加元素的时候，将它上一次出现的位置+1的地方的值加1，然后在其本身位置+1的值打上个-1标记，这样就成了线性求值，也就是每次求getsum(a[i].l)
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define M 1000005 int n,m,C; int a[M],ans[M],c[M],pre[M],last[M]; struct node{int l,r,id;}q[M]; bool cmp(node x,node y){return x.r<y.r;} void updata(int x,int v){ for(int i=x;i<=n;i+=i&(-i)) c[i]+=v; } int query(int x){ int ret=0; for(int i=x;i>0;i-=i&(-i)) ret+=c[i]; return ret; } void work() { int now=0; for(int i=1;i<=m;i++) { while(now<q[i].r) now++,updata(pre[now]+1,1),updata(now+1,-1);//树状数组的第一个元素只能从1开始 ans[q[i].id]=query(q[i].l); } for(int i=1;i<=m;i++) printf("%d\n",ans[i]); } void init() { cin>>n; for(int i=1,x;i<=n;i++) scanf("%d",&a[i]),pre[i]=last[a[i]],last[a[i]]=i; cin>>m; 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); } int main() { init(); work(); return 0; }莫队
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define M 50500 int tp,now; int n,m,blo; int a[M],pos[M],cnt[M],ans[M*4],map[1000005]; struct node{int l,r,id;}q[M*4]; inline int ID(int x){return map[x]?map[x]:map[x]=++tp;} bool cmp(node x,node y){return pos[x.l]<pos[y.l]||(pos[x.l]==pos[y.l]&&x.r<y.r);} void update(int x,int v) { cnt[x]+=v; if(v==1&&cnt[x]==1) now++; if(v==-1&&!cnt[x]) now--; } void work() { int l=1,r=0; for(int i=1;i<=m;i++) { while(r<q[i].r) update(a[++r],1); while(l>q[i].l) update(a[--l],1); while(r>q[i].r) update(a[r--],-1); while(l<q[i].l) update(a[l++],-1); ans[q[i].id]=now; } for(int i=1;i<=m;i++) printf("%d\n",ans[i]); } void init() { cin>>n;blo=sqrt(n); for(int i=1,x;i<=n;i++){ scanf("%d",&x); a[i]=ID(x); pos[i]=(i-1)/blo+1; } cin>>m; 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); } int main() { init(); work(); return 0; }