区间不同数的个数-树状数组/线段树/莫队/主席树-编程阁

引言

数据结构	时间复杂度	实现难度
树状数组(Fenwick-Tree)	O ( m log ⁡ n ) O(m \log n)O(mlogn)	⭐ (简单)
线段树(Segment-Tree)	O ( m log ⁡ n ) O(m \log n)O(mlogn)	⭐⭐ (中等)
莫队(Mo)	O ( n n ) O(n \sqrt n)O(nn)	⭐⭐ (中等)
主席树(可持久化线段树)	O ( ( n + m ) log ⁡ n ) O((n + m)\log n)O((n+m)logn)	⭐⭐⭐ (困难)

题目-HH的项链

离线-树状数组解法

树状数组维护当前数组出现的位置信息, 具体的来说

为了保证时间复杂度, 要求指针r rr一直单调
对于当前遍历到的数字w ww, 如果出现过那么将上一次出现的位置− 1 -1−1
然后将当前位置记录l a s t i = j last_i = jlasti=j
然后j jj枚举下一个位置

因为j jj指针只会走一次, 算法时间复杂度O ( m log ⁡ n ) O(m \log n)O(mlogn)

核心代码

sort(q+1,q+m+1);intj=1;for(inti=1;i<=m;++i){intl=q[i].l,r=q[i].r,id=q[i].id;while(j<=r){if(last[w[j]])add(last[w[j]],-1);add(j,1);last[w[j]]=j;j++;}ans[id]=get(r)-get(l-1);}

代码实现

#include<bits/stdc++.h>usingnamespacestd;constintN=50010,M=2e5+10,S=1e6+10;intn,m;intw[N];structAsk{intl,r,id;booloperator<(constAsk&a)const{returnr<a.r;}}q[M];inttr[S],last[S],ans[M];inlineintlowbit(intx){returnx&-x;}voidadd(intu,intx){for(inti=u;i<S;i+=lowbit(i))tr[i]+=x;}intget(intu){intans=0;for(inti=u;i;i-=lowbit(i))ans+=tr[i];returnans;}intmain(){ios::sync_with_stdio(false);cin.tie(0);cin>>n;for(inti=1;i<=n;++i)cin>>w[i];cin>>m;for(inti=1;i<=m;++i){intl,r;cin>>l>>r;q[i]={l,r,i};}sort(q+1,q+m+1);intj=1;for(inti=1;i<=m;++i){intl=q[i].l,r=q[i].r,id=q[i].id;while(j<=r){if(last[w[j]])add(last[w[j]],-1);add(j,1);last[w[j]]=j;j++;}ans[id]=get(r)-get(l-1);}for(inti=1;i<=m;++i)cout<<ans[i]<<'\n';return0;}

离线-线段树解法

因为树状数组维护的是位置的前缀和,线段树也可以解决

代码实现

#include<bits/stdc++.h>usingnamespacestd;constintN=50010,M=2e5+10,S=1e6+10;intn,m;intw[N];structAsk{intl,r,id;booloperator<(constAsk&a)const{returnr<a.r;}}q[M];intlast[S],ans[M];structNode{intl,r;intsum;}tr[N<<2];voidpushup(intu){tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;}voidbuild(intu,intl,intr){tr[u]={l,r,0};if(l==r)return;intmid=l+r>>1;build(u<<1,l,mid);build(u<<1|1,mid+1,r);pushup(u);}voidmodify(intu,intpos,intx){if(tr[u].l==tr[u].r){tr[u].sum+=x;return;}intmid=tr[u].l+tr[u].r>>1;if(pos<=mid)modify(u<<1,pos,x);if(pos>mid)modify(u<<1|1,pos,x);pushup(u);}intquery(intu,intql,intqr){if(tr[u].l>=ql&&tr[u].r<=qr)returntr[u].sum;intans=0;intmid=tr[u].l+tr[u].r>>1;if(ql<=mid)ans+=query(u<<1,ql,qr);if(qr>mid)ans+=query(u<<1|1,ql,qr);returnans;}inlineintlowbit(intx){returnx&-x;}intmain(){ios::sync_with_stdio(false);cin.tie(0);cin>>n;for(inti=1;i<=n;++i)cin>>w[i];cin>>m;for(inti=1;i<=m;++i){intl,r;cin>>l>>r;q[i]={l,r,i};}build(1,1,n);sort(q+1,q+m+1);intj=1;for(inti=1;i<=m;++i){auto[l,r,id]=q[i];while(j<=r){if(last[w[j]])modify(1,last[w[j]],-1);modify(1,j,1);last[w[j]]=j;j++;}ans[id]=query(1,l,r);}for(inti=1;i<=m;++i)cout<<ans[i]<<'\n';return0;}

离线-莫队算法

假设最坏情况下, 每次查询一个区间n nn, 开一个数组用于记录每个数字出现的次数, 算法时间复杂度O ( q n ) O(qn)O(qn), 无法通过

莫队优化

开一个c n t cntcnt数组用来记录每个数字出现的次数

( 1 ) (1)(1)对查询区间进行排序

假设当前查询区间是[ i , j ] [i, j][i,j]

蓝色部分是下一段查询的区间

( 2 ) (2)(2)对于每个区间

首先移动j jj指针, 移动到下一次查询的右端点上, 同时对于当前数字x xx, 如果未出现过那么不同数字的数量+ 1 +1+1, 否则不同数字的出现次数不发生变化, 同时累计c n t cntcnt数组的值
再将指针i ii移动到下一次查询的左端点, 对于当前需要删除的数字x xx, 如果出现次数大于1 11, 那么c n t ( x ) − 1 cnt(x) - 1cnt(x)−1, 不对答案产生影响, 否则答案− 1 -1−1

因为每次移动指针最坏情况下是O ( n ) O(n)O(n)次, 算法时间复杂度最坏O ( q n ) O(qn)O(qn), 还是没办法通过

算法核心优化:因为算法瓶颈在指针会移动O ( n q ) O(nq)O(nq)次数, 尝试使得右指针是单调的(不会向回移动),左指针分块, 具体的来说

区间左端点按照分块的编号排序,双关键字排序

如果分块编号相同按照区间右端点从小到大排序
如果分块编号不同, 块小的在前面

将所有查询分为n \sqrt nn块, 每一块长度是也是n \sqrt nn,块内部区间的右端点是递增的

对于右指针来说,块内走的次数不会超过n nn, 一共n \sqrt nn块, 最多移动n n n \sqrt nnn次

左指针分为两种情况

块内最多移动n \sqrt nn次, 最多q qq个询问, 算法时间复杂度最差O ( q n ) O(q \sqrt n)O(qn)
块间最多移动2 n 2 \sqrt n2n次, 最多跨越n − 1 \sqrt n - 1n−1个块, 最差O ( 2 n ) O(2n)O(2n)

因此左指针的最差时间复杂度是O ( q n ) O(q \sqrt n)O(qn)

左右时间取最大值, 因此优化后的算法时间复杂度最坏情况下是O ( q n ) O(q \sqrt n)O(qn)

假设块的大小是a aa, 右指针的移动次数是n 2 a \frac{n ^ 2}{a}an2, 左指针的最大移动次数是m a mama, 也就是
a = n 2 m a = \sqrt {\frac{n ^ 2}{m}}a=mn2
左右指针移动的次数相当

如果a = n a = \sqrt na=n比较慢, 尝试将a aa变为n 2 m \sqrt {\frac{n ^ 2}{m}}mn2

核心代码

// i表示左端点, j表示右端点for(intk=0,i=1,j=0,res=0;k<m;++k){// l, r分别代表当前区间的左右端点auto[l,r,id]=q[k];while(j<r)add(w[++j],res);while(j>r)del(w[j--],res);while(i<l)del(w[i++],res);while(i>l)add(w[--i],res);ans[id]=res;}

示例代码

#include<bits/stdc++.h>usingnamespacestd;constintN=50010,M=2e5+10,S=1e6+10;intn,m,len;intw[N],cnt[S],ans[M];structAsk{intl,r,id;}q[M];intget(inti){returni/len;}boolcmp(constAsk&a,constAsk&b){intba=get(a.l),bb=get(b.l);if(ba==bb)returna.r<b.r;returnba<bb;}voidadd(intx,int&ans){if(!cnt[x])ans++;cnt[x]++;}voiddel(intx,int&ans){cnt[x]--;if(!cnt[x])ans--;}intmain(){ios::sync_with_stdio(false);cin.tie(0);cin>>n;for(inti=1;i<=n;++i)cin>>w[i];cin>>m;// 计算块长len=sqrt(n*n/m+1);for(inti=0;i<m;++i){intl,r;cin>>l>>r;q[i]={l,r,i};}sort(q,q+m,cmp);for(intk=0,i=1,j=0,res=0;k<m;++k){auto[l,r,id]=q[k];while(j<r)add(w[++j],res);while(j>r)del(w[j--],res);while(i<l)del(w[i++],res);while(i>l)add(w[--i],res);ans[id]=res;}for(inti=0;i<m;++i)cout<<ans[i]<<'\n';return0;}

在线-主席树(持久化线段树)

假设对于当前数字上一次出现的位置是l a s t i last_ilasti

那么当前区间[ l , r ] [l, r][l,r]内是第一次出现该数字等价于l a s t i < l last_i < llasti<l, 为了方便统计定义g ( i ) g(i)g(i)表示l a s t i + 1 last_i + 1lasti+1

那么答案就是统计在区间[ l , r ] [l, r][l,r]内g ( i ) ≤ l g(i) \le lg(i)≤l的数字的个数, 可以使用主席树维护g ( i ) g(i)g(i)的取值

查询的时候直接查询≤ l \le l≤l的所有g ( i ) g(i)g(i)就是答案

算法时间复杂度O ( m log ⁡ n ) O(m \log n)O(mlogn)

代码实现

构建多个版本根节点数组r o o t [ N ] root[N]root[N]
构建初始版本主席树
对每个g ( i ) g(i)g(i)执行插入操作O ( n log ⁡ n ) O(n \log n)O(nlogn)
计算区间和, 版本查询l − 1 , r l - 1, rl−1,r两个版本O ( m log ⁡ n ) O(m \log n)O(mlogn)

#include<bits/stdc++.h>usingnamespacestd;constintN=50010,M=2e5+10,S=1e6+10;intn,m;intw[N];structNode{intls,rs;ints;}tr[4*N+17*N];intlast[S],g[N];introot[M],idx;intbuild(intl,intr){intu=++idx;tr[u]={0,0,0};if(l==r)returnu;intmid=l+r>>1;tr[u].ls=build(l,mid);tr[u].rs=build(mid+1,r);returnu;}intinsert(intp,intl,intr,intx){intu=++idx;tr[u]=tr[p];tr[u].s=tr[p].s+1;if(l==r)returnu;intmid=l+r>>1;if(x<=mid)tr[u].ls=insert(tr[p].ls,l,mid,x);if(x>mid)tr[u].rs=insert(tr[p].rs,mid+1,r,x);returnu;}intquery(intp,intq,intl,intr,intql,intqr){if(l>=ql&&r<=qr)returntr[q].s-tr[p].s;intans=0;intmid=l+r>>1;if(ql<=mid)ans+=query(tr[p].ls,tr[q].ls,l,mid,ql,qr);if(qr>mid)ans+=query(tr[p].rs,tr[q].rs,mid+1,r,ql,qr);returnans;}intmain(){ios::sync_with_stdio(false);cin.tie(0);cin>>n;root[0]=build(1,n);for(inti=1;i<=n;++i){cin>>w[i];g[i]=last[w[i]]+1;last[w[i]]=i;root[i]=insert(root[i-1],1,n,g[i]);}cin>>m;while(m--){intl,r;cin>>l>>r;// 注意这里查询的是 <= l的g[i]的数量intans=query(root[l-1],root[r],1,n,1,l);cout<<ans<<'\n';}return0;}