本题其实主要就这几点：
1.离线，以右端点排序(从小到大);
2.建立树状数组c[],c[i]表示从1~i中有多少种不同的数字；
3.对于每次查询的答案就是sum(r)-sum(l-1);
4.由于问题是离线排序回答，所以应该注意输出顺序(离散化前的顺序)；
Q：直接统计前缀和，然后对于每次询问O(1)输出不行吗？
A：当然不行，因为仅仅确保了sum[r]的正确性，无法确保sum[l-1]的正确性；比如说：1 2 3 1 1 1 ，区间[2,5]的个数是3，然而sum[5]=3,sum[1]=1,sum[5]-sum[1]=2；(原因是第一位的1在sum[5]和sum[1]中都算了一遍)
Q：为什么要离散化？
A：为了保证我们从左到右扫描扫到i时确保当存在a[i]时1~i中树状数组的答案；这样可以保证不仅仅sum(r)的正确性，也可以保证sum(l-1)的正确性；
#include <bits/stdc++.h> using namespace std; int n,m; int a[5000010]; struct haha{ int pos; int l; int r; }lala[5000010]; bool cmp(haha x,haha y) { return x.r<y.r; } int c[5000010]; inline int lowbit(int x) { return x&(-x); } void add(int x,int value) { while(x<=n){ c[x]+=value; x+=lowbit(x); } return; } int sum(int x) { int res=0; while(x>0){ res+=c[x]; x-=lowbit(x); } return res; } int nxt[1000010]; int ans[1000010]; int main () { cin>>n; for(register int i=1;i<=n;i++){ scanf("%d",&a[i]); } cin>>m; for(register int i=1;i<=m;i++){ int l,r; scanf("%d%d",&l,&r); lala[i].pos=i; lala[i].l=l; lala[i].r=r; } sort(lala+1,lala+1+m,cmp); int st=1; for(register int i=1;i<=m;i++){ for(register int j=st;j<=lala[i].r;j++){ if(nxt[a[j]]){ add(nxt[a[j]],-1); } add(j,1); nxt[a[j]]=j; } st=lala[i].r+1; ans[lala[i].pos]=sum(lala[i].r)-sum(lala[i].l-1); } for(int i=1;i<=m;i++){ cout<<ans[i]<<endl; } }
原文：https://www.cnblogs.com/kamimxr/p/11320296.html