莫队 · ooliver

P2709 【模板】莫队 / 小B的询问模板，直接看代码吧： #include using namespace std; #define int long long const int N=5e4+5; int n,m,k,siz,sum; int a[N],c[N],ans[N]; struct ask { int l,r,id; bool operator>n>>m>>k; siz=sqrt(n); for (int i=1;i>a[i]; for (int i=1;i>q[i].l>>q[i].r,q[i].id=i; sort(q+1,q+m+1); int l=1,r=0; for (int i=1;iq[i].l) l--,add(a[l]); while (rq[i].r) del(a[r]),r--; ans[q[i].id]=sum; } for (int i=1;i `#include using namespace std; #define int long long const int N=5e4+5; int n,m,k,siz,sum; int a[N],c[N],ans[N]; struct ask { int l,r,id; bool operator(const ask &a)const { if ((l-1)/siz==(a.l-1)/siz) return ra.r; return l/siza.l/siz; } }q[N]; void add(int x) { sum-=c[x]*c[x]; c[x]++; sum+=c[x]*c[x]; } void del(int x) { sum-=c[x]*c[x]; c[x]--; sum+=c[x]*c[x]; } signed main(){ cin>>n>>m>>k; siz=sqrt(n); for (int i=1;i>a[i]; for (int i=1;i>q[i].l>>q[i].r,q[i].id=i; sort(q+1,q+m+1); int l=1,r=0; for (int i=1;i while (l>q[i].l) l--,add(a[l]); while (rq[i].r) r++,add(a[r]); while (lq[i].l) del(a[l]),l++; while (r>q[i].r) del(a[r]),r--; ans[q[i].id]=sum; } for (int i=1;ians[i] return 0; }` P1494 [国家集训队] 小 Z 的袜子考虑枚举每种颜色的式子，会发现展开后要维护的就是区间种类平方和，与板子一样，代码： #include using namespace std; #define int long long const int N=5e4+5; int n,m,siz,sum; int a[N],c[N],ans1[N],ans2[N]; struct ask { int l,r,id; bool operator>n>>m; siz=sqrt(n); for (int i=1;i>a[i]; for (int i=1;i>q[i].l>>q[i].r,q[i].id=i; sort(q+1,q+m+1); int l=1,r=0; for (int i=1;iq[i].l) l--,add(a[l]); while (rq[i].r) del(a[r]),r--; int len=q[i].r-q[i].l+1; int fz=sum-len,fm=len*(len-1); ans1[q[i].id]=fz/__gcd(fz,fm),ans2[q[i].id]=fm/__gcd(fz,fm); } for (int i=1;i `#include using namespace std; #define int long long const int N=5e4+5; int n,m,siz,sum; int a[N],c[N],ans1[N],ans2[N]; struct ask { int l,r,id; bool operator(const ask &a)const { if ((l-1)/siz==(a.l-1)/siz) return ra.r; return l/siza.l/siz; } }q[N]; void add(int x) { sum-=c[x]*c[x]; c[x]++; sum+=c[x]*c[x]; } void del(int x) { sum-=c[x]*c[x]; c[x]--; sum+=c[x]*c[x]; } signed main(){ cin>>n>>m; siz=sqrt(n); for (int i=1;i>a[i]; for (int i=1;i>q[i].l>>q[i].r,q[i].id=i; sort(q+1,q+m+1); int l=1,r=0; for (int i=1;i if(q[i].l==q[i].r){ ans1[q[i].id]=0,ans2[q[i].id]=1; continue; } while (l>q[i].l) l--,add(a[l]); while (rq[i].r) r++,add(a[r]); while (lq[i].l) del(a[l]),l++; while (r>q[i].r) del(a[r]),r--; int len=q[i].r-q[i].l+1; int fz=sum-len,fm=len*(len-1); ans1[q[i].id]=fz/__gcd(fz,fm),ans2[q[i].id]=fm/__gcd(fz,fm); } for (int i=1;ians1[i]"/"ans2[i]"\n"; return 0; }` P4462 [CQOI2018] 异或序列异或前缀和一下，式子就能转化成两个下标之间的关系。用一个桶装每个值的数量，莫队移动区间计算即可。代码： #include using namespace std; #define int long long const int N=1e5+5; int n,m,k,siz,sum; int a[N],tag[N],ans[N]; struct ask { int l,r,id; bool operator>n>>m>>k; siz=sqrt(n),tag[0]=1; for (int i=1;i>a[i],a[i]^=a[i-1]; for (int i=1;i>q[i].l>>q[i].r,q[i].id=i; sort(q+1,q+m+1); int l=0,r=0; tag[0]=1; for (int i=1;iq[i].r) del(a[r]),r--; while (l>q[i].l-1) l--,add(a[l]); while (r `#include using namespace std; #define int long long const int N=1e5+5; int n,m,k,siz,sum; int a[N],tag[N],ans[N]; struct ask { int l,r,id; bool operator(const ask &a)const { if ((l-1)/siz==(a.l-1)/siz) return ra.r; return l/siza.l/siz; } }q[N]; void add(int x) { sum+=tag[k^x]; tag[x]++; } void del(int x) { tag[x]--; sum-=tag[k^x]; } signed main(){ cin>>n>>m>>k; siz=sqrt(n),tag[0]=1; for (int i=1;i>a[i],a[i]^=a[i-1]; for (int i=1;i>q[i].l>>q[i].r,q[i].id=i; sort(q+1,q+m+1); int l=0,r=0; tag[0]=1; for (int i=1;i while (lq[i].l-1) del(a[l]),l++; while (r>q[i].r) del(a[r]),r--; while (l>q[i].l-1) l--,add(a[l]); while (rq[i].r) r++,add(a[r]); ans[q[i].id]=sum; } for (int i=1;ians[i]"\n"; return 0; }` P3709 大爷的字符串题发现最优时是把序列变成若干个连续上升序列拼接，而数量就应该是区间众数。所以用莫队维护区间众数即可。代码： #include using namespace std; #define int long long const int N=2e5+5; int n,m,k,siz,sum; int a[N],b[N],cnt[N],t[N],ans[N]; struct ask { int l,r,id; bool operator>n>>m; siz=sqrt(n); for (int i=1;i>a[i],b[i]=a[i]; sort(b+1,b+1+n); for(int i=1;i>q[i].l>>q[i].r,q[i].id=i; sort(q+1,q+m+1); int l=1,r=0; for (int i=1;iq[i].l) l--,add(a[l]); while (rq[i].r) del(a[r]),r--; ans[q[i].id]=sum; } for (int i=1;i `#include using namespace std; #define int long long const int N=2e5+5; int n,m,k,siz,sum; int a[N],b[N],cnt[N],t[N],ans[N]; struct ask { int l,r,id; bool operator(const ask &a)const { if ((l-1)/siz==(a.l-1)/siz) return ra.r; return l/siza.l/siz; } }q[N]; void add(int x) { t[cnt[x]]--; t[++cnt[x]]++; sum=max(sum,cnt[x]); } void del(int x) { t[cnt[x]]--; if(cnt[x]==sum&&!t[cnt[x]]) sum--; t[--cnt[x]]++; } signed main(){ cin>>n>>m; siz=sqrt(n); for (int i=1;i>a[i],b[i]=a[i]; sort(b+1,b+1+n); for(int i=1;ia[i]=lower_bound(b+1,b+1+n,a[i])-b; for (int i=1;i>q[i].l>>q[i].r,q[i].id=i; sort(q+1,q+m+1); int l=1,r=0; for (int i=1;i while (l>q[i].l) l--,add(a[l]); while (rq[i].r) r++,add(a[r]); while (lq[i].l) del(a[l]),l++; while (r>q[i].r) del(a[r]),r--; ans[q[i].id]=sum; } for (int i=1;ians[i]"\n"; return 0; }` P5906 【模板】回滚莫队&不删除莫队也是模板，代码： #include using namespace std; #define int long long const int N=4e5+5; const int M=sqrt(N)+5; int n,m,k,siz,now; int st[M],ed[M]; int a[N],b[N],qz[N],hz[N],hz2[N],cnt[N],ans[N],cnt2[N]; struct ask{ int l,r,id; bool operator>n; for(int i=1;i>a[i],b[i]=a[i]; siz=sqrt(n*1.0),k=ceil(n*1.0/(siz*1.0)); sort(b+1,b+1+n); for(int i=1;i>m; for(int i=1;i>q[i].l>>q[i].r,q[i].id=i; sort(q+1,q+m+1); int id=0; for(int i=1;i=L&&q[id+1].lq[id].l){ l--; if(!hz2[a[l]]) hz2[a[l]]=l; tmp2=max(tmp2,max(hz2[a[l]],hz[a[l]])-l); } ans[q[id].id]=max(now,tmp2); now=tmp; while(l `#include using namespace std; #define int long long const int N=4e5+5; const int M=sqrt(N)+5; int n,m,k,siz,now; int st[M],ed[M]; int a[N],b[N],qz[N],hz[N],hz2[N],cnt[N],ans[N],cnt2[N]; struct ask{ int l,r,id; bool operator(const ask &a)const{ if((l-1)/siz+1==(a.l-1)/siz+1) return ra.r; return (l-1)/siza.l-1)/siz; } }q[N]; void add(int x){ qz[a[x]]=min(qz[a[x]],x); hz[a[x]]=max(hz[a[x]],x); now=max(now,hz[a[x]]-qz[a[x]]); } void del(int x){hz2[a[x]]=0;} int get(int l,int r){ int res=0; for(int i=l;icnt[a[i]]=0; for(int i=l;i if(!cnt[a[i]]) cnt[a[i]]=i; res=max(res,i-cnt[a[i]]); } return res; } signed main(){ memset(qz,0x3f,sizeof qz); cin>>n; for(int i=1;i>a[i],b[i]=a[i]; siz=sqrt(n*1.0),k=ceil(n*1.0/(siz*1.0)); sort(b+1,b+1+n); for(int i=1;ia[i]=lower_bound(b+1,b+1+n,a[i])-b; cin>>m; for(int i=1;i>q[i].l>>q[i].r,q[i].id=i; sort(q+1,q+m+1); int id=0; for(int i=1;i memset(qz,0x3f,sizeof qz); memset(hz,0,sizeof hz); now=0; int L=(i-1)*siz+1,R=min(i*siz,n); int l=R+1,r=R; while(q[id+1].l>=L&&q[id+1].l1 id++; if(q[id].r ans[q[id].id]=get(q[id].l,q[id].r); continue; } while(rq[id].r) r++,add(r); int tmp=now; int tmp2=0; while(l>q[id].l){ l--; if(!hz2[a[l]]) hz2[a[l]]=l; tmp2=max(tmp2,max(hz2[a[l]],hz[a[l]])-l); } ans[q[id].id]=max(now,tmp2); now=tmp; while(ldel(l),l++; } } for (int i=1;ians[i]"\n"; return 0; }` P14420 [JOISC 2014] 历史的研究 / Historical Research 发现莫队时增加一个元素很好写，但删一个就不好维护了，所以考虑回滚莫队。代码： #include using namespace std; #define int long long const int N=1e5+5; const int M=sqrt(N)+5; int n,m,k,siz,now; int st[M],ed[M]; int a[N],b[N],cnt[N],ans[N],cnt2[N]; struct ask{ int l,r,id; bool operator>n>>m; siz=sqrt(n*1.0),k=ceil(n*1.0/(siz*1.0)); for(int i=1;i>a[i],b[i]=a[i]; sort(b+1,b+1+n); for(int i=1;i>q[i].l>>q[i].r,q[i].id=i; sort(q+1,q+m+1); int id=0; for(int i=1;i=L&&q[id+1].lq[id].l) l--,add(l); ans[q[id].id]=now; now=tmp; while(l `#include using namespace std; #define int long long const int N=1e5+5; const int M=sqrt(N)+5; int n,m,k,siz,now; int st[M],ed[M]; int a[N],b[N],cnt[N],ans[N],cnt2[N]; struct ask{ int l,r,id; bool operator(const ask &a)const{ if((l-1)/siz+1==(a.l-1)/siz+1) return ra.r; return (l-1)/siza.l-1)/siz; } }q[N]; void add(int x){ cnt[a[x]]++; now=max(now,cnt[a[x]]*b[a[x]]); } void del(int x){cnt[a[x]]--;} int get(int l,int r){ int res=0; for(int i=l;icnt2[a[i]]=0; for(int i=l;i cnt2[a[i]]++; res=max(res,cnt2[a[i]]*b[a[i]]); } return res; } signed main(){ cin>>n>>m; siz=sqrt(n*1.0),k=ceil(n*1.0…