其實(shí)樹上莫隊(duì)是一個(gè)歐拉序而已嘛，像普通的莫隊(duì)，特判一下出現(xiàn)過兩次的值就行了

設(shè) \(st_i\) 為 \(i\) 進(jìn)棧的時(shí)間，\(ed_i\) 為 \(i\) 出棧的時(shí)間，\(dfn_x<dfn_y\) ，那么就可以分兩種情況：

1、\(y\) 在 \(x\) 子樹中，也就是 \(LCA(x,y)=x\)，那么區(qū)間轉(zhuǎn)化成 \([st_x,st_y]\)

2、\(y\) 不在 \(x\) 子樹中，也就是 \(LCA(x,y)\not =x\)，那么區(qū)間轉(zhuǎn)化成 \([ed_x,st_y]\)

然后就是板子了

for(int i=1;i<=m;i++){x=read(),y=read();q[i].anc=LCA(x,y);q[i].id=i;if(x==q[i].anc||y==q[i].anc){q[i].anc=0;q[i].l=st[x];q[i].r=st[y];if(q[i].l>q[i].r) q[i].l=st[y],q[i].r=st[x];}else {q[i].l=ed[x];q[i].r=st[y];if(q[i].l>q[i].r) q[i].l=ed[y],q[i].r=st[x];} }

1、SP10707 COT2 - Count on a tree II

其實(shí)我國慶的時(shí)候就學(xué)了，只不過我一直 \(WA\)...后來從倍增換成樹剖，重構(gòu)一遍代碼就 \(A\) 了

\(Code\ Below:\)

#include <bits/stdc++.h> using namespace std; const int maxn=100000+10; int n,m,a[maxn],mp[maxn],vis[maxn],cnt[maxn],ans[maxn],st[maxn],ed[maxn],p[maxn<<1],tim,blo,now; int head[maxn],to[maxn<<1],nxt[maxn<<1],tot; int top[maxn],dep[maxn],siz[maxn],son[maxn],fa[maxn];struct Query{int l,r,anc,id; }q[maxn];bool cmp(Query a,Query b){if((a.l-1)/blo!=(b.l-1)/blo)return (a.l-1)/blo<(b.l-1)/blo;return a.r<b.r; }inline int read(){register int x=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}return (f==1)?x:-x; } inline void add(int x,int y){to[++tot]=y;nxt[tot]=head[x];head[x]=tot; }void dfs1(int x,int f){siz[x]=1;fa[x]=f;dep[x]=dep[f]+1;st[x]=++tim;p[tim]=x;int maxson=-1;for(int i=head[x],y;i;i=nxt[i]){y=to[i];if(y==f) continue;dfs1(y,x);siz[x]+=siz[y];if(maxson<siz[y]){maxson=siz[y];son[x]=y;}}ed[x]=++tim;p[tim]=x; }void dfs2(int x,int topf){top[x]=topf;if(son[x]) dfs2(son[x],topf);for(int i=head[x],y;i;i=nxt[i]){y=to[i];if(y==fa[x]||y==son[x]) continue;dfs2(y,y);} }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]];}if(dep[x]>dep[y]) swap(x,y);return x; }int update(int x){if(vis[x]){if(--cnt[a[x]]==0) now--;}else if(++cnt[a[x]]==1) now++;vis[x]^=1; }int main() {n=read(),m=read();blo=sqrt(n);for(int i=1;i<=n;i++) mp[i]=a[i]=read();sort(mp+1,mp+n+1);int t=unique(mp+1,mp+n+1)-mp-1;for(int i=1;i<=n;i++) a[i]=lower_bound(mp+1,mp+t+1,a[i])-mp;int x,y;for(int i=1;i<n;i++){x=read(),y=read();add(x,y);add(y,x);}dfs1(1,0);dfs2(1,1);for(int i=1;i<=m;i++){x=read(),y=read();q[i].anc=LCA(x,y);q[i].id=i;if(x==q[i].anc||y==q[i].anc){q[i].anc=0;q[i].l=st[x];q[i].r=st[y];if(q[i].l>q[i].r) q[i].l=st[y],q[i].r=st[x];}else {q[i].l=ed[x];q[i].r=st[y];if(q[i].l>q[i].r) q[i].l=ed[y],q[i].r=st[x];}}sort(q+1,q+m+1,cmp);int L=1,R=0;for(int i=1;i<=m;i++){while(R<q[i].r) update(p[++R]);while(R>q[i].r) update(p[R--]);while(L<q[i].l) update(p[L++]);while(L>q[i].l) update(p[--L]);if(q[i].anc) update(q[i].anc);ans[q[i].id]=now;if(q[i].anc) update(q[i].anc);}for(int i=1;i<=m;i++) printf("%d\n",ans[i]);return 0; }

2、蘋果樹（本地Cena自測(cè)）

其實(shí)就是特判一下 \(cnt_a\) 和 \(cnt_b\)

只不過我非常傻，離散了一下顏色，就 \(GG\) 了

\(Code\ Below:\)

#include <cstdio> #include <cctype> #include <cmath> #include <algorithm> using namespace std; const int maxn=100000+10; int n,m,a[maxn],mp[maxn],vis[maxn],cnt[maxn],ans[maxn],st[maxn],ed[maxn],p[maxn<<1],tim,blo,now; int head[maxn],to[maxn<<1],nxt[maxn<<1],tot; int top[maxn],dep[maxn],siz[maxn],son[maxn],fa[maxn];struct Query{int l,r,a,b,anc,id; }q[maxn];bool cmp(Query a,Query b){if((a.l-1)/blo!=(b.l-1)/blo)return (a.l-1)/blo<(b.l-1)/blo;return a.r<b.r; }inline int read(){register int x=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}return (f==1)?x:-x; } inline void add(int x,int y){to[++tot]=y;nxt[tot]=head[x];head[x]=tot; }void dfs1(int x,int f){siz[x]=1;fa[x]=f;dep[x]=dep[f]+1;st[x]=++tim;p[tim]=x;int maxson=-1;for(int i=head[x],y;i;i=nxt[i]){y=to[i];if(y==f) continue;dfs1(y,x);siz[x]+=siz[y];if(maxson<siz[y]){maxson=siz[y];son[x]=y;}}ed[x]=++tim;p[tim]=x; }void dfs2(int x,int topf){top[x]=topf;if(son[x]) dfs2(son[x],topf);for(int i=head[x],y;i;i=nxt[i]){y=to[i];if(y==fa[x]||y==son[x]) continue;dfs2(y,y);} }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]];}if(dep[x]>dep[y]) swap(x,y);return x; }void update(int x){if(vis[x]){if(--cnt[a[x]]==0) now--;}else if(++cnt[a[x]]==1) now++;vis[x]^=1; }int main() {n=read(),m=read();blo=sqrt(2*n);for(int i=1;i<=n;i++) a[i]=read();int x,y;for(int i=1;i<=n;i++){x=read(),y=read();if(x&&y) add(x,y),add(y,x);}dfs1(1,0);dfs2(1,1);for(int i=1;i<=m;i++){x=read(),y=read(),q[i].a=read(),q[i].b=read();q[i].anc=LCA(x,y);q[i].id=i;if(x==q[i].anc||y==q[i].anc){q[i].anc=0;q[i].l=st[x];q[i].r=st[y];if(q[i].l>q[i].r) q[i].l=st[y],q[i].r=st[x];}else {q[i].l=ed[x];q[i].r=st[y];if(q[i].l>q[i].r) q[i].l=ed[y],q[i].r=st[x];}}sort(q+1,q+m+1,cmp);int L=1,R=0;for(int i=1;i<=m;i++){while(R<q[i].r) update(p[++R]);while(R>q[i].r) update(p[R--]);while(L<q[i].l) update(p[L++]);while(L>q[i].l) update(p[--L]);if(q[i].anc) update(q[i].anc);ans[q[i].id]=now;if(q[i].a!=q[i].b&&cnt[q[i].a]&&cnt[q[i].b]) ans[q[i].id]--;if(q[i].anc) update(q[i].anc);}for(int i=1;i<=m;i++) printf("%d\n",ans[i]);return 0; }

3、Haruna’s Breakfast

小知識(shí)：帶修莫隊(duì)塊大小在 \(n^{\frac 23}\) 跑的最快……不過我不會(huì)證

本人錯(cuò)誤點(diǎn)：莫隊(duì)修改過來的時(shí)候應(yīng)該先將修改的時(shí)間戳 \(+1\)，再更新；莫隊(duì)修改回去的時(shí)候應(yīng)該先更新，再將修改的時(shí)間戳 \(-1\)

\(Code\ Below:\)

#include <bits/stdc++.h> using namespace std; const int maxn=100000+10; int n,m,a[maxn],mp[maxn],pos[maxn],val[maxn],vis[maxn],cnt[maxn],ans[maxn],st[maxn],ed[maxn],p[maxn<<1],tim,blo,now,Cnum,Qnum,an; int head[maxn],to[maxn<<1],nxt[maxn<<1],tot; int top[maxn],dep[maxn],siz[maxn],son[maxn],fa[maxn];struct Query{int l,r,anc,pre,id; }q[maxn];bool cmp(Query a,Query b){if((a.l-1)/blo!=(b.l-1)/blo)return (a.l-1)/blo<(b.l-1)/blo;if(a.r!=b.r) return a.r<b.r;return a.pre<b.pre; }inline int read(){register int x=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}return (f==1)?x:-x; } inline void add(int x,int y){to[++tot]=y;nxt[tot]=head[x];head[x]=tot; }void dfs1(int x,int f){siz[x]=1;fa[x]=f;dep[x]=dep[f]+1;st[x]=++tim;p[tim]=x;int maxson=-1;for(int i=head[x],y;i;i=nxt[i]){y=to[i];if(y==f) continue;dfs1(y,x);siz[x]+=siz[y];if(maxson<siz[y]){maxson=siz[y];son[x]=y;}}ed[x]=++tim;p[tim]=x; }void dfs2(int x,int topf){top[x]=topf;if(son[x]) dfs2(son[x],topf);for(int i=head[x],y;i;i=nxt[i]){y=to[i];if(y==fa[x]||y==son[x]) continue;dfs2(y,y);} }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]];}if(dep[x]>dep[y]) swap(x,y);return x; }inline void update(int x){if(a[x]<maxn){if(vis[x]){if(--cnt[a[x]]==0) now=min(now,a[x]);}else if(++cnt[a[x]]==1) while(cnt[now]) now++;}vis[x]^=1; }inline void Del(int x){if(vis[x]&&a[x]<maxn) if(--cnt[a[x]]==0) now=min(now,a[x]);} inline void Add(int x){if(vis[x]&&a[x]<maxn) if(++cnt[a[x]]==1) while(cnt[now]) now++;}int main() {n=read(),m=read();blo=pow(2*n,0.666666);for(int i=1;i<=n;i++) a[i]=read();int opt,x,y;for(int i=1;i<n;i++){x=read(),y=read();add(x,y);add(y,x);}dfs1(1,0);dfs2(1,1);for(int i=1;i<=m;i++){opt=read(),x=read(),y=read();if(opt==0){pos[++Qnum]=x;val[Qnum]=y;}else {q[++Cnum].anc=LCA(x,y);q[Cnum].pre=Qnum;q[Cnum].id=Cnum;if(x==q[Cnum].anc||y==q[Cnum].anc){q[Cnum].anc=0;q[Cnum].l=st[x];q[Cnum].r=st[y];if(q[Cnum].l>q[Cnum].r) q[Cnum].l=st[y],q[Cnum].r=st[x];}else {q[Cnum].l=ed[x];q[Cnum].r=st[y];if(q[Cnum].l>q[Cnum].r) q[Cnum].l=ed[y],q[Cnum].r=st[x];}}}sort(q+1,q+Cnum+1,cmp);int L=1,R=0;for(int i=1;i<=Cnum;i++){while(R<q[i].r) update(p[++R]);while(R>q[i].r) update(p[R--]);while(L<q[i].l) update(p[L++]);while(L>q[i].l) update(p[--L]);if(q[i].anc) update(q[i].anc);while(an<q[i].pre){an++;Del(pos[an]);swap(a[pos[an]],val[an]);Add(pos[an]);}while(an>q[i].pre){Del(pos[an]);swap(a[pos[an]],val[an]);Add(pos[an]);an--;}ans[q[i].id]=now;if(q[i].anc) update(q[i].anc);}for(int i=1;i<=Cnum;i++) printf("%d\n",ans[i]);return 0; }

4、GT and trees

綜合題，求樹上路徑待修改區(qū)間眾數(shù)，不難想到帶修樹上莫隊(duì)

然后就再記錄一個(gè) \(f[i]\) 表示區(qū)間出現(xiàn) \(i\) 次的數(shù)的個(gè)數(shù)，\(add\) 沒什么好說的，\(del\) 就暴力找，跟 \(mex\) 一樣

\(Code\ Below:\)

#include <cstdio> #include <cctype> #include <cmath> #include <cstring> #include <algorithm> using namespace std; const int maxn=100000+10; int n,m,a[maxn],vis[maxn],f[maxn],cnt[maxn],pos[maxn],val[maxn]; int Ans[maxn],st[maxn],ed[maxn],p[maxn<<1],tim,blo,Cnum,Qnum,ans,now; int head[maxn],to[maxn<<1],nxt[maxn<<1],tot; int top[maxn],dep[maxn],siz[maxn],son[maxn],fa[maxn];struct Query{int l,r,anc,pre,id; }q[maxn];bool cmp(Query a,Query b){if((a.l-1)/blo!=(b.l-1)/blo)return (a.l-1)/blo<(b.l-1)/blo;if(a.r!=b.r) return a.r<b.r;return a.pre<b.pre; }inline int read(){register int x=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}return (f==1)?x:-x; } inline void add(int x,int y){to[++tot]=y;nxt[tot]=head[x];head[x]=tot; }void dfs1(int x,int f){siz[x]=1;fa[x]=f;dep[x]=dep[f]+1;st[x]=++tim;p[tim]=x;int maxson=-1;for(int i=head[x],y;i;i=nxt[i]){y=to[i];if(y==f) continue;dfs1(y,x);siz[x]+=siz[y];if(maxson<siz[y]){maxson=siz[y];son[x]=y;}}ed[x]=++tim;p[tim]=x; }void dfs2(int x,int topf){top[x]=topf;if(son[x]) dfs2(son[x],topf);for(int i=head[x],y;i;i=nxt[i]){y=to[i];if(y==fa[x]||y==son[x]) continue;dfs2(y,y);} }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]];}if(dep[x]>dep[y]) swap(x,y);return x; }inline void update(int x){if(vis[x]){if(--f[cnt[a[x]]--]==0) while(!f[ans]) ans--;}else if(++f[++cnt[a[x]]]==1) ans=max(ans,cnt[a[x]]);vis[x]^=1; }inline void Add(int x){if(vis[x]) if(++f[++cnt[a[x]]]==1) ans=max(ans,cnt[a[x]]);} inline void Del(int x){if(vis[x]) if(--f[cnt[a[x]]--]==0) while(!f[ans]) ans--;}int main() {int T=read();while(T--){memset(head,0,sizeof(head));memset(son,0,sizeof(son));memset(vis,0,sizeof(vis));memset(f,0,sizeof(f));memset(cnt,0,sizeof(cnt));tim=tot=Cnum=Qnum=ans=now=0;n=read(),m=read();blo=pow(2*n,0.666666);int opt,x,y;for(int i=1;i<n;i++){x=read(),y=read();add(x,y);add(y,x);}for(int i=1;i<=n;i++) a[i]=read();dfs1(1,0);dfs2(1,1);for(int i=1;i<=m;i++){opt=read(),x=read(),y=read();if(opt==0) pos[++Qnum]=x,val[Qnum]=y;else {q[++Cnum].anc=LCA(x,y);q[Cnum].pre=Qnum;q[Cnum].id=Cnum;if(x==q[Cnum].anc||y==q[Cnum].anc){q[Cnum].anc=0;if(st[x]<st[y]) q[Cnum].l=st[x],q[Cnum].r=st[y];else q[Cnum].l=st[y],q[Cnum].r=st[x];}else {if(ed[x]<st[y]) q[Cnum].l=ed[x],q[Cnum].r=st[y];else q[Cnum].l=ed[y],q[Cnum].r=st[x];}}}sort(q+1,q+Cnum+1,cmp);int L=1,R=0;for(int i=1;i<=Cnum;i++){while(R<q[i].r) update(p[++R]);while(R>q[i].r) update(p[R--]);while(L<q[i].l) update(p[L++]);while(L>q[i].l) update(p[--L]);if(q[i].anc) update(q[i].anc);while(now<q[i].pre){now++;Del(pos[now]);swap(a[pos[now]],val[now]);Add(pos[now]);}while(now>q[i].pre){Del(pos[now]);swap(a[pos[now]],val[now]);Add(pos[now]);now--;}Ans[q[i].id]=ans;if(q[i].anc) update(q[i].anc);}for(int i=1;i<=Cnum;i++) printf("%d\n",Ans[i]);}return 0; }

5、[WC2013]糖果公園

樹上帶修莫隊(duì) 我20分鐘切掉的

其實(shí)差不多一個(gè)板子，不過我被卡常了，我 \(inline+register+O_2\) 才過，最大一個(gè)點(diǎn) \(5136ms\)

// luogu-judger-enable-o2 #include <bits/stdc++.h> #define res register int #define ll long long using namespace std; const int maxn=100000+10; int n,m,Q,c[maxn],v[maxn],w[maxn],vis[maxn],cnt[maxn],pos[maxn],val[maxn],st[maxn],ed[maxn],p[maxn<<1],tim,blo,Cnum,Qnum,now; int head[maxn],to[maxn<<1],nxt[maxn<<1],tot;ll Ans[maxn],ans; int top[maxn],dep[maxn],siz[maxn],son[maxn],fa[maxn];struct Query{int l,r,anc,pre,id; }q[maxn];bool cmp(Query a,Query b){if((a.l-1)/blo!=(b.l-1)/blo)return (a.l-1)/blo<(b.l-1)/blo;if(a.r<b.r) return a.r<b.r;return a.pre<b.pre; }inline int read(){register int x=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}return (f==1)?x:-x; } inline void add(res x,res y){to[++tot]=y;nxt[tot]=head[x];head[x]=tot; }void dfs1(res x,res f){siz[x]=1;fa[x]=f;dep[x]=dep[f]+1;st[x]=++tim;p[tim]=x;int maxson=-1;for(int i=head[x],y;i;i=nxt[i]){y=to[i];if(y==f) continue;dfs1(y,x);siz[x]+=siz[y];if(maxson<siz[y]){maxson=siz[y];son[x]=y;}}ed[x]=++tim;p[tim]=x; }void dfs2(res x,res topf){top[x]=topf;if(son[x]) dfs2(son[x],topf);for(int i=head[x],y;i;i=nxt[i]){y=to[i];if(y==fa[x]||y==son[x]) continue;dfs2(y,y);} }inline int LCA(res x,res y){while(top[x]!=top[y]){if(dep[top[x]]<dep[top[y]]) swap(x,y);x=fa[top[x]];}if(dep[x]>dep[y]) swap(x,y);return x; }inline void update(res x){if(vis[x]){ans-=(ll)v[c[x]]*w[cnt[c[x]]--];}else ans+=(ll)v[c[x]]*w[++cnt[c[x]]];vis[x]^=1; }inline void Del(res x){if(vis[x]) ans-=(ll)v[c[x]]*w[cnt[c[x]]--];} inline void Add(res x){if(vis[x]) ans+=(ll)v[c[x]]*w[++cnt[c[x]]];}int main() {n=read(),m=read(),Q=read();blo=pow(2*n,0.666666);for(res i=1;i<=m;i++) v[i]=read();for(res i=1;i<=n;i++) w[i]=read();res opt,x,y;for(res i=1;i<n;i++){x=read(),y=read();add(x,y);add(y,x);}dfs1(1,0);dfs2(1,1);for(res i=1;i<=n;i++) c[i]=read();for(res i=1;i<=Q;i++){opt=read(),x=read(),y=read();if(opt==0) pos[++Qnum]=x,val[Qnum]=y;else {q[++Cnum].anc=LCA(x,y);q[Cnum].pre=Qnum;q[Cnum].id=Cnum;if(x==q[Cnum].anc||y==q[Cnum].anc){q[Cnum].anc=0;if(st[x]<st[y]) q[Cnum].l=st[x],q[Cnum].r=st[y];else q[Cnum].l=st[y],q[Cnum].r=st[x];}else {if(ed[x]<st[y]) q[Cnum].l=ed[x],q[Cnum].r=st[y];else q[Cnum].l=ed[y],q[Cnum].r=st[x];}}}sort(q+1,q+Cnum+1,cmp);res L=1,R=0;for(res i=1;i<=Cnum;i++){while(R<q[i].r) update(p[++R]);while(R>q[i].r) update(p[R--]);while(L<q[i].l) update(p[L++]);while(L>q[i].l) update(p[--L]);if(q[i].anc) update(q[i].anc);while(now<q[i].pre){now++;Del(pos[now]);swap(c[pos[now]],val[now]);Add(pos[now]);}while(now>q[i].pre){Del(pos[now]);swap(c[pos[now]],val[now]);Add(pos[now]);now--;}Ans[q[i].id]=ans;if(q[i].anc) update(q[i].anc);}for(res i=1;i<=Cnum;i++) printf("%lld\n",Ans[i]);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/owencodeisking/p/10018392.html

總結(jié)

以上是生活随笔為你收集整理的[学习笔记]树上莫队的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。