欢迎访问~原文出处——
题意概括
给出一个长度为n的序列,用m次询问,问区间Li~Ri中有多少种不同的数。
0<=数值<=1000000,n<=50000,m<=200000
题解
本题有许多做法。
这里介绍树状数组和莫队,都是离线算法。
树状数组
我们把序列按照R从小到大排序。
然后从左往右走。
依次加入数字,当前的状态,比如说搞定了前i个数字。
对于第i+1个数字,我们要给它做一个标记,但是不可以重复,那么最优的方案就是把它之前的那个位置的+1标记删除,放到这里来。
于是对于搞定前i个数的时候,有且一定有对于某一个数值,如果它出现过,那么它的+1标记在最后出现的那个地方。
为什么可以?因为R是递增的!
然后就是维护一个点修改和区间和的东西了。秒选树状数组。
莫队
莫队就是最裸的莫队。
先把1~n的区间尽量平均的分成sqrt(n)块。
把所有的询问以L所在的块为第一关键字升序,R为第二关键字升序排序。
然后就是大暴力。
朴素的写法有点长。
但是压缩之后短的无厘头……
代码
代码1 - 树状数组
#include#include #include #include #include using namespace std;const int N=50000+5,M=200000+5,V=1000000+5;int n,m,a[N],c[N],pos[V];struct Query{ int L,R,bh,ans; bool operator < (const Query x) const { return R 0;x-=lowbit(x)) ans+=c[x]; 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++){ scanf("%d%d",&q[i].L,&q[i].R); q[i].bh=i; } sort(q+1,q+m+1); memset(pos,0,sizeof pos); memset(c,0,sizeof c); for (int i=1,j=0;i<=m;i++){ while (j
代码2 - 莫队
#include#include #include #include #include using namespace std;const int N=50000+5,M=200000+5,V=1000000+5;int n,m,size,a[N],cnt[V];struct Query{ int L,R,bh,ans;}q[M];bool cmpmd(Query a,Query b){ int k1=a.L/size,k2=b.L/size; if (k1!=k2) return k1 q[i].L){ L--; if (cnt[a[L]]==0) tot++; cnt[a[L]]++; } while (R>q[i].R){ cnt[a[R]]--; if (cnt[a[R]]==0) tot--; R--; } while (L
代码3 - 莫队+代码压缩
#include#include #include #include #include using namespace std;const int N=50000+5,M=200000+5,V=1000000+5;int n,m,size,a[N],cnt[V];struct Query{ int L,R,bh,ans;}q[M];bool cmpmd(Query a,Query b){ int k1=a.L/size,k2=b.L/size; if (k1!=k2) return k1 q[i].L) tot+=cnt[a[--L]]++==0; while (R>q[i].R) tot-=--cnt[a[R--]]==0; while (L