P2709 【模板】莫队 / 小B的询问
模板，直接看代码吧：
#include<bits/stdc++.h>
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 r<a.r;
return l/siz<a.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<=n;i++) cin>>a[i];
for (int i=1;i<=m;i++) cin>>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<=m;i++) {
while (l>q[i].l) l--,add(a[l]);
while (r<q[i].r) r++,add(a[r]);
while (l<q[i].l) del(a[l]),l++;
while (r>q[i].r) del(a[r]),r--;
ans[q[i].id]=sum;
}
for (int i=1;i<=m;i++) cout<<ans[i]<<endl;
return 0;
}P1494 [国家集训队] 小 Z 的袜子
考虑枚举每种颜色的式子，会发现展开后要维护的就是区间种类平方和，与板子一样，代码：
#include<bits/stdc++.h>
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 r<a.r;
return l/siz<a.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<=n;i++) cin>>a[i];
for (int i=1;i<=m;i++) cin>>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<=m;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 (r<q[i].r) r++,add(a[r]);
while (l<q[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;i<=m;i++) cout<<ans1[i]<<"/"<<ans2[i]<<"\n";
return 0;
}P4462 [CQOI2018] 异或序列
异或前缀和一下，式子就能转化成两个下标之间的关系。
用一个桶装每个值的数量，莫队移动区间计算即可。
代码：
#include<bits/stdc++.h>
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 r<a.r;
return l/siz<a.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<=n;i++) cin>>a[i],a[i]^=a[i-1];
for (int i=1;i<=m;i++) cin>>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<=m;i++) {
while (l<q[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 (r<q[i].r) r++,add(a[r]);
ans[q[i].id]=sum;
}
for (int i=1;i<=m;i++) cout<<ans[i]<<"\n";
return 0;
}P3709 大爷的字符串题
发现最优时是把序列变成若干个连续上升序列拼接，而数量就应该是区间众数。
所以用莫队维护区间众数即可。
代码：
#include<bits/stdc++.h>
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 r<a.r;
return l/siz<a.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<=n;i++) cin>>a[i],b[i]=a[i];
sort(b+1,b+1+n);
for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+n,a[i])-b;
for (int i=1;i<=m;i++) cin>>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<=m;i++) {
while (l>q[i].l) l--,add(a[l]);
while (r<q[i].r) r++,add(a[r]);
while (l<q[i].l) del(a[l]),l++;
while (r>q[i].r) del(a[r]),r--;
ans[q[i].id]=sum;
}
for (int i=1;i<=m;i++) cout<<-ans[i]<<"\n";
return 0;
}P5906 【模板】回滚莫队&不删除莫队
也是模板，代码：
#include<bits/stdc++.h>
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 r<a.r;
return (l-1)/siz<(a.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;i<=r;i++) cnt[a[i]]=0;
for(int i=l;i<=r;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<=n;i++) cin>>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<=n;i++) a[i]=lower_bound(b+1,b+1+n,a[i])-b;
cin>>m;
for(int i=1;i<=m;i++) cin>>q[i].l>>q[i].r,q[i].id=i;
sort(q+1,q+m+1);
int id=0;
for(int i=1;i<=k;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].l<=R&&id+1<=m){
id++;
if(q[id].r<=R){
ans[q[id].id]=get(q[id].l,q[id].r);
continue;
}
while(r<q[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(l<=R) del(l),l++;
}
}
for (int i=1;i<=m;i++) cout<<ans[i]<<"\n";
return 0;
}P14420 [JOISC 2014] 历史的研究 / Historical Research
发现莫队时增加一个元素很好写，但删一个就不好维护了，所以考虑回滚莫队。
代码：
#include<bits/stdc++.h>
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 r<a.r;
return (l-1)/siz<(a.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;i<=r;i++) cnt2[a[i]]=0;
for(int i=l;i<=r;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/(siz*1.0));
for(int i=1;i<=n;i++) cin>>a[i],b[i]=a[i];
sort(b+1,b+1+n);
for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+n,a[i])-b;
for(int i=1;i<=m;i++) cin>>q[i].l>>q[i].r,q[i].id=i;
sort(q+1,q+m+1);
int id=0;
for(int i=1;i<=k;i++){
memset(cnt,0,sizeof cnt);
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].l<=R&&id+1<=m){
id++;
if(q[id].r<=R){
ans[q[id].id]=get(q[id].l,q[id].r);
continue;
}
while(r<q[id].r) r++,add(r);
int tmp=now;
while(l>q[id].l) l--,add(l);
ans[q[id].id]=now;
now=tmp;
while(l<=R) del(l),l++;
}
}
for (int i=1;i<=m;i++) cout<<ans[i]<<"\n";
return 0;
}P4137 Rmq Problem / mex
用 bitset 维护当前信息，用 _Find_first() 函数求 mex 即可。
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5;
int n,m,k,siz;
int a[N],sum[N],ans[N];
bitset<N> now;
struct ask{
int l,r,id;
bool operator<(const ask &a)const{
if((l-1)/siz==(a.l-1)/siz) return r<a.r;
return l/siz<a.l/siz;
}
}q[N];
void add(int x){
sum[x]++;
now[x]=1;
}
void del(int x){
sum[x]--;
if(!sum[x]) now[x]=0;
}
signed main(){
cin>>n>>m;
siz=sqrt(n);
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=m;i++) cin>>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<=m;i++){
while (l>q[i].l) l--,add(a[l]);
while (r<q[i].r) r++,add(a[r]);
while (l<q[i].l) del(a[l]),l++;
while (r>q[i].r) del(a[r]),r--;
ans[q[i].id]=(~now)._Find_first();
}
for (int i=1;i<=m;i++) cout<<ans[i]<<"\n";
return 0;
}P8078 [WC2022] 秃子酋长
用链表维护前后关系，这时删除一个元素比较好实现，但增加一个元素并不好实现，所以考虑回滚莫队。
在莫队回溯时用栈维护删除元素顺序，倒序恢复即可。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n,m,siz,tp;
long long now;
int a[N],inv[N],stk[N],lst[N],nxt[N];
long long ans[N];
struct ask{
int l,r,id;
bool operator<(const ask &a)const{
int bl=(l-1)/siz,ba=(a.l-1)/siz;
if(bl!=ba)return bl<ba;
return r>a.r;
}
}q[N];
inline void del(int x,int f){
int v=a[x],p=lst[v],s=nxt[v];
if(f) stk[++tp]=x;
if(p>=1&&s<=n) now+=abs(inv[p]-inv[s]);
if(p>=1) now-=abs(inv[p]-inv[v]);
if(s<=n) now-=abs(inv[v]-inv[s]);
nxt[p]=s;lst[s]=p;
}
inline void back(int x){
int v=a[x],p=lst[v],s=nxt[v];
if(p>=1&&s<=n) now-=abs(inv[p]-inv[s]);
if(p>=1) now+=abs(inv[p]-inv[v]);
if(s<=n) now+=abs(inv[v]-inv[s]);
nxt[p]=v,lst[s]=v;
}
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i],inv[a[i]]=i;
siz=n/sqrt(m);
for(int i=1;i<=m;i++) cin>>q[i].l>>q[i].r,q[i].id=i;
sort(q+1,q+m+1);
for(int i=0;i<=n+1;i++) lst[i]=i-1,nxt[i]=i+1;
for(int i=1;i<n;i++) now+=abs(inv[i]-inv[i+1]);
int cur=1,L=1;
for(int i=0;i<=(n-1)/siz;i++){
int qL=i*siz+1;
while(L<qL) del(L++,0);
long long now1=now;
int r=n;
tp=0;
while(cur<=m&&(q[cur].l-1)/siz==i){
while(r>q[cur].r) del(r--,1);
long long tmp=now;
int l=L,rtp=tp;
while(l<q[cur].l) del(l++,1);
ans[q[cur].id]=now;
while(tp>rtp) back(stk[tp--]);
now=tmp,cur++;
}
while(tp) back(stk[tp--]);
now=now1;
}
for(int i=1;i<=m;i++) cout<<ans[i]<<"\n";
return 0;
}P4074 [WC2013] 糖果公园
树上带修莫队。
这里使用括号序列把树映射成序列，主要原理是记录 dfs 时进入和离开每个节点的顺序。
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5;
vector<int> g[N];
int fa[N],son[N],top[N],siz[N],dep[N];
int idx,st[N],ed[N],a[N];
int n,m,k,bs,v[N],w[N],c[N];
int pos[N],nc[N],vis[N],cnt[N],ans[N],sum,num;
struct node{
int l,r,t,id,lc;
bool operator<(const node b){
if(l/bs!=b.l/bs) return l<b.l;
if(r/bs!=b.r/bs) return r<b.r;
return t<b.t;
}
}q[N];
void dfs1(int u,int f){
fa[u]=f,siz[u]=1,dep[u]=dep[f]+1;
for(int v:g[u]){
if(v==f) continue;
dfs1(v,u);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]]) son[u]=v;
}
}
void dfs2(int u,int topf){
st[u]=++idx,top[u]=topf,a[idx]=u;
if(son[u]) dfs2(son[u],topf);
for(int v:g[u]){
if(v==fa[u]||v==son[u]) continue;
dfs2(v,v);
}
ed[u]=++idx,a[idx]=u;
}
int lca(int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
x=fa[top[x]];
}
return (dep[x]<dep[y]?x:y);
}
void add(int x){
vis[x]^=1;
if(vis[x]) sum+=w[++cnt[c[x]]]*v[c[x]];
else sum-=w[cnt[c[x]]--]*v[c[x]];
}
void solve(){
bs=pow(2*n,2.0/3);
sort(q+1,q+1+num);
int l=1,r=0,t=0;
for(int i=1;i<=num;i++){
while(l>q[i].l) l--,add(a[l]);
while(r<q[i].r) r++,add(a[r]);
while(l<q[i].l) add(a[l]),l++;
while(r>q[i].r) add(a[r]),r--;
while(t<q[i].t){
t++;
if(vis[pos[t]]){
add(pos[t]);
swap(c[pos[t]],nc[t]);
add(pos[t]);
}
else swap(c[pos[t]],nc[t]);
}
while(t>q[i].t){
if(vis[pos[t]]){
add(pos[t]);
swap(c[pos[t]],nc[t]);
add(pos[t]);
}
else swap(c[pos[t]],nc[t]);
t--;
}
ans[q[i].id]=sum;
if(q[i].lc) ans[q[i].id]+=w[cnt[c[q[i].lc]]+1]*v[c[q[i].lc]];
}
}
signed main(){
cin>>n>>m>>k;
for(int i=1;i<=m;i++) cin>>v[i];
for(int i=1;i<=n;i++) cin>>w[i];
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs1(1,0);
dfs2(1,1);
for(int i=1;i<=n;i++) cin>>c[i];
for(int i=1,t=0;i<=k;i++){
int ty,x,y;
cin>>ty>>x>>y;
if(ty==1){
int lc=lca(x,y);
q[++num].t=t;
q[num].id=num;
if(st[x]>st[y]) swap(x,y);
if(lc==x){
q[num].l=st[x];
q[num].r=st[y];
}
else{
q[num].l=ed[x];
q[num].r=st[y];
q[num].lc=lc;
}
}
else{
pos[++t]=x;
nc[t]=y;
}
}
solve();
for(int i=1;i<=num;i++) cout<<ans[i]<<"\n";
return 0;
}P5268 [SNOI2017] 一个简单的询问
把函数拆成两个差分的前缀和函数相乘，一个询问拆成四个询问，这样就很好写了。
详细实现原理很简单，可以看代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e5+5;
int n,m,idx,siz,now;
int a[N],suml[N],sumr[N],ans[N];
struct ask{
int l,r,tag,id;
bool operator<(const ask &a)const{
if ((l-1)/siz==(a.l-1)/siz) return r<a.r;
return l/siz<a.l/siz;
}
}q[N];
signed main(){
cin>>n;
siz=sqrt(n);
for(int i=1;i<=n;i++) cin>>a[i];
cin>>m;
for(int i=1;i<=m;i++){
int l1,l2,r1,r2;
cin>>l1>>r1>>l2>>r2;
q[++idx]=(ask){r1,r2,1,i};
q[++idx]=(ask){r1,l2-1,-1,i};
q[++idx]=(ask){r2,l1-1,-1,i};
q[++idx]=(ask){l1-1,l2-1,1,i};
}
sort(q+1,q+1+idx);
int l=0,r=0;
for(int i=1;i<=idx;i++){
while(l<q[i].l) l++,suml[a[l]]++,now+=sumr[a[l]];
while(l>q[i].l) suml[a[l]]--,now-=sumr[a[l]],l--;
while(r<q[i].r) r++,sumr[a[r]]++,now+=suml[a[r]];
while(r>q[i].r) sumr[a[r]]--,now-=suml[a[r]],r--;
ans[q[i].id]+=now*q[i].tag;
}
for(int i=1;i<=m;i++) cout<<ans[i]<<"\n";
return 0;
}P4689 [Ynoi Easy Round 2016] 这是我自己的发明
和上一题很像，难点是换根。
考虑不换根就直接 dfs 序，子树是连续的。
我们钦定一个根节点 1，要换的根 与查询的节点 在以 1 为根时有两种关系。
- 不在 子树内，那 的子树其实不会变。
- 在 子树内，那 的子树就变成了同时为 的儿子和 的祖先的点子树外的所有点。
根据以上性质写就行了，代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5,M=2e6+5;
int n,m,rt=1,idx,siz,now,id;
int fa[N][21],d[N],son[N],dfn[N],low[N],tim;
int a[N],a1[N],b[N],suml[N],sumr[N],ans[M];
vector<int> g[N];
struct ask{
int l,r,tag,id;
bool operator<(const ask &o)const{
int bl=l/siz,obl=o.l/siz;
if(bl!=obl) return bl<obl;
return (bl&1)?(r<o.r):(r>o.r);
}
}q[M*4];
struct path{int u,v;};
void add(int l1,int r1,int l2,int r2,int i){
auto push=[&](int L,int R,int T){
if(L<=0||R<=0) return;
if(L>R) swap(L,R);
q[++idx]={L,R,T,i};
};
push(r1,r2,1);
push(r1,l2-1,-1);
push(r2,l1-1,-1);
push(l1-1,l2-1,1);
}
void dfs(int u,int f){
dfn[u]=++tim,fa[u][0]=f,d[u]=d[f]+1,son[u]=1;
for(int i=1;i<=19;i++) fa[u][i]=fa[fa[u][i-1]][i-1];
for(int v:g[u]) if(v!=f) dfs(v,u),son[u]+=son[v];
low[u]=tim;
}
int find(int u,int k){
for(int i=19;i>=0;i--) if(k&(1<<i)) u=fa[u][i];
return u;
}
vector<path> get(int u){
if(rt==u) return {{1,n}};
if(dfn[rt]<dfn[u]||dfn[rt]>low[u]) return {{dfn[u],low[u]}};
int f=find(rt,d[rt]-d[u]-1);
vector<path> res;
if(dfn[f]>1) res.push_back({1,dfn[f]-1});
if(low[f]<n) res.push_back({low[f]+1,n});
return res;
}
signed main(){
ios::sync_with_stdio(0);cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a1[i],b[i]=a1[i];
sort(b+1,b+1+n);
int tot=unique(b+1,b+1+n)-b-1;
for(int i=1;i<=n;i++) a1[i]=lower_bound(b+1,b+tot,a1[i])-b;
for(int i=1;i<n;i++){
int u,v;cin>>u>>v;
g[u].push_back(v);g[v].push_back(u);
}
dfs(1,0);
for(int i=1;i<=n;i++) a[dfn[i]]=a1[i];
for(int i=1;i<=m;i++){
int op,x,y;cin>>op;
if(op==1) cin>>rt;
else{
id++;cin>>x>>y;
vector<path> x1=get(x),y1=get(y);
for(auto &i:x1) for(auto &j:y1) add(i.u,i.v,j.u,j.v,id);
}
}
siz=max(1LL,(int)(n/sqrt(max(1LL,idx))));
sort(q+1,q+1+idx);
int cl=0,cr=0;
for(int i=1;i<=idx;i++){
while(cl<q[i].l) cl++,suml[a[cl]]++,now+=sumr[a[cl]];
while(cl>q[i].l) now-=sumr[a[cl]],suml[a[cl]]--,cl--;
while(cr<q[i].r) cr++,sumr[a[cr]]++,now+=suml[a[cr]];
while(cr>q[i].r) now-=suml[a[cr]],sumr[a[cr]]--,cr--;
ans[q[i].id]+=now*q[i].tag;
}
for(int i=1;i<=id;i++) cout<<ans[i]<<"\n";
return 0;
}
Comments NOTHING