莫队
jiangjiangQwQ · · 算法·理论
阅读材料
Alex_wei的博客
训练题单
例题
- 板子题P2709\
左端点所在的块的编号相同直接按右端点排序，否则按左端点排序。
::::info[Code]
#include<bits/stdc++.h> #include<algorithm> using namespace std; #define int long long const int N=5e4+5; int n,m,k; int a[N],B; struct Query{ int l,r,id; bool operator<(const Query &o)const{ if(l/B!=o.l/B) return l<o.l; return r<o.r; } }q[N]; int cnt[N],sum; void add(int x){ sum-=cnt[x]*cnt[x]; cnt[x]++; sum+=cnt[x]*cnt[x]; } void del(int x){ sum-=cnt[x]*cnt[x]; cnt[x]--; sum+=cnt[x]*cnt[x]; } signed main(){ cin>>n>>m>>k; B=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); vector<int> ans(m+1,0); for(int i=1,l=1,r=0;i<=m;i++){ while(l>q[i].l) add(a[--l]); while(r<q[i].r) add(a[++r]); while(l<q[i].l) del(a[l++]); while(r>q[i].r) del(a[r--]); ans[q[i].id]=sum; } for(int i=1;i<=m;i++) cout<<ans[i]<<'\n'; return 0; } /* 1 2054 765 */::::
- 板子题P1494
::::info[Code]
#include<bits/stdc++.h> #include<algorithm> using namespace std; #define int long long const int N=5e5+5; int n,m,a[N],B; struct node{ int l,r,id; bool operator<(const node &o)const{ if(l/B!=o.l/B) return l<o.l; if((l/B)&1) return r<o.r; return r>o.r; } }q[N]; int cnt[N],sum; void add(int x){ sum+=cnt[x]; cnt[x]++; } void del(int x){ cnt[x]--; sum-=cnt[x]; } int ans1[N],ans2[N]; signed main(){ cin>>n>>m;B=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); for(int i=1,l=1,r=0;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) add(a[--l]); while(r<q[i].r) add(a[++r]); while(l<q[i].l) del(a[l++]); while(r>q[i].r) del(a[r--]); ans1[q[i].id]=sum,ans2[q[i].id]=(r-l+1)*(r-l)/2; } for(int i=1;i<=m;i++){ if(ans1[i]){ int w=__gcd(ans1[i],ans2[i]); ans1[i]/=w,ans2[i]/=w; }else ans2[i]=1; cout<<ans1[i]<<'/'<<ans2[i]<<'\n'; } return 0; } /* 1 2054 765 */::::
- 带修莫队P1903\
与普通莫队的排序不同，左端点所在块的编号不同按照左端点排序，右端点所在块的编号不同按右端点排序，否则记
tim 为这个询问之前的修改操作数，按tim 升序排序。 ::::info[Code]#include<bits/stdc++.h> #include<algorithm> using namespace std; #define int long long const int N=1e6+5; int n,m; int c[N]; int qc,rc,B,sum; struct node{ int l,r,id,tim; bool operator<(const node &o)const{ if(l/B!=o.l/B) return l<o.l; if(r/B!=o.r/B) return r<o.r; return tim<o.tim; } }; node Q[N],R[N]; int cnt[N]; void add(int x){ cnt[x]++; if(cnt[x]==1) sum++; } void del(int x){ cnt[x]--; if(!cnt[x]) sum--; } int ans[N]; signed main(){ ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); cin>>n>>m;B=pow(n,0.666); for(int i=1;i<=n;i++) cin>>c[i]; for(int i=1;i<=m;i++){ char op; int l,r,p,c; cin>>op; if(op=='Q') cin>>l>>r,Q[++qc]={l,r,qc,rc}; else cin>>p>>c,R[++rc]={p,c,i,0}; }sort(Q+1,Q+qc+1); for(int i=1,l=1,r=0,x=0;i<=qc;i++){ while(l>Q[i].l) add(c[--l]); while(r<Q[i].r) add(c[++r]); while(l<Q[i].l) del(c[l++]); while(r>Q[i].r) del(c[r--]); while(x<Q[i].tim){ int p=R[++x].l; if(l<=p&&p<=r) del(c[p]),add(R[x].r); swap(c[p],R[x].r); } while(x>Q[i].tim){ int p=R[x].l; if(l<=p&&p<=r) del(c[p]),add(R[x].r); swap(c[p],R[x--].r); }ans[Q[i].id]=sum; // cout<<i<<' '<<x<<' '<<l<<' '<<r<<' '<<sum<<' '<<Q[i].id<<'\n'; } for(int i=1;i<=qc;i++) cout<<ans[i]<<'\n'; return 0; }::::
- 树上莫队\
将树转化为 Euler 序，记
st_u,ed_u 分别为第一次访问、回溯的时间戳。下图的 Euler 序为(1,2,4,5,5,6,6,7,7,4,2,3,3) 。如果u 在v 的子树中，如(u=6,v=2) ，拿出(st_2,st_6) 这段区间，出现一次的点就在这条链上。否则的话比如(u=5,v=3) ，拿出(ed_5,st_3) ，这段区间需保证st_u<st_v ，不然 swap 一下。同样的手法只是还需要加上 lca。可以开一个 use 数组记录一个点有没有被加入，use_u = 0 就加入，否则删除。操作完成对use_u 异或1 即可。排序可普排也可奇偶优化排。注意st,ed 长度开2n 。
::::info[Code]
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
#define int long long
#define ls(c) c<<1
#define rs(c) c<<1|1
const int N=8e4+5,M=2e5;
int n,m,a[N];
int lsh[N],tot;
vector<int> edge[N];
void add(int a,int b){
edge[a].push_back(b);
}
int fu[N],fa[N][22],sz[N],dep[N];
int st[N],ed[N],e[N],k,son[N];
void dfs1(int u,int Fa){
sz[u]=1;dep[u]=dep[Fa]+1;
fu[u]=Fa;e[++k]=u;st[u]=k;
for(int i=1;i<=20;i++) fa[u][i]=fa[fa[u][i-1]][i-1];
for(auto v:edge[u]){
if(v==Fa) continue;
fa[v][0]=u;
dfs1(v,u);
sz[u]+=sz[v];
if(sz[v]>sz[son[u]]) son[u]=v;
}e[++k]=u;ed[u]=k;
}
int top[N],dfn[N],dfncnt,B;
void dfs2(int u,int head){
top[u]=head,dfn[u]=++dfncnt;
if(son[u]) dfs2(son[u],head);
for(auto v:edge[u]){
if(v!=fu[u]&&v!=son[u]) dfs2(v,v);
}
}
int LCA(int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
x=fu[top[x]];
}if(dep[x]>dep[y]) swap(x,y);
return x;
}
struct Q{
int l,r,id,lca;
bool operator<(const Q &o)const{
if(l/B!=o.l/B) return l<o.l;
if((l/B)&1) return r<o.r;
return r>o.r;
}
}q[M];
int used[N],res,c[N];
void calc(int x){
if(!used[x]&&(++c[a[x]]==1)) res++;
if(used[x]&&(--c[a[x]]==0)) res--;
used[x]^=1;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i],lsh[++tot]=a[i];
sort(lsh+1,lsh+tot+1);
tot=unique(lsh+1,lsh+tot+1)-lsh-1;
for(int i=1;i<=n;i++) a[i]=lower_bound(lsh+1,lsh+tot+1,a[i])-lsh;
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
add(u,v),add(v,u);
}
dfs1(1,0),dfs2(1,1);
B=2*n/sqrt(m*2/3);
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
q[i].id=i;q[i].lca=LCA(u,v);
if(st[u]>st[v]) swap(u,v);
if(q[i].lca==u){
q[i].l=st[u],q[i].r=st[v];q[i].lca=0;
}else{
q[i].l=ed[u],q[i].r=st[v];
}
}sort(q+1,q+m+1);
vector<int> ans(m+1,0);
for(int i=1,l=1,r=0;i<=m;i++){
while(l>q[i].l) calc(e[--l]);
while(r<q[i].r) calc(e[++r]);
while(l<q[i].l) calc(e[l++]);
while(r>q[i].r) calc(e[r--]);
if(q[i].lca) calc(q[i].lca);
ans[q[i].id]=res;
if(q[i].lca) calc(q[i].lca);
}
for(int i=1;i<=m;i++) cout<<ans[i]<<'\n';
return 0;
}
::::