https://www.luogu.com.cn/problem/P4074
树上离线带修改的莫队板题
把这两题混了一下
https://blog.csdn.net/liufengwei1/article/details/109153421
https://blog.csdn.net/liufengwei1/article/details/109173023
(其实还可以改成求个区间最大值套个回滚莫队
#include<bits/stdc++.h> using namespace std; const int maxl=2e5+10; int n,m,qn,qcnt,ccnt,len; int a[maxl],idx[maxl],bel[maxl],dep[maxl]; int num[maxl],ll[maxl],rr[maxl],vis[maxl]; long long w[maxl],val[maxl],ans[maxl]; int f[21][maxl]; vector<int> e[maxl]; struct qry { int l,r,lca,t,id; }q[maxl]; struct mdf { int pos,col; }c[maxl]; inline void dfs(int u,int fa) { idx[++n]=u;ll[u]=n; for(int v:e[u]) if(fa!=v) { f[0][v]=u;dep[v]=dep[u]+1; dfs(v,u); } idx[++n]=u;rr[u]=n; } inline int getlca(int u,int v) { if(dep[u]<dep[v]) swap(u,v); for(int i=20;i>=0;i--) if((dep[u]-dep[v])>>i&1) u=f[i][u]; if(u==v) return u; for(int i=20;i>=0;i--) if(f[i][u]!=f[i][v]) u=f[i][u],v=f[i][v]; return f[0][u]; } inline bool cmp(const qry&a,const qry&b) { if(bel[a.l]^bel[b.l]) return bel[a.l]<bel[b.l]; if(bel[a.r]^bel[b.r]) return bel[a.r]<bel[b.r]; return a.t<b.t; } inline void prework() { scanf("%d%d%d",&n,&m,&qn); for(int i=1;i<=m;i++) scanf("%lld",&val[i]); for(int i=1;i<=n;i++) scanf("%lld",&w[i]); int u,v; for(int i=1;i<=n-1;i++) { scanf("%d%d",&u,&v); e[u].push_back(v); e[v].push_back(u); } for(int i=1;i<=n;i++) scanf("%d",&a[i]); int opt,x,y;qcnt=0;ccnt=0; for(int i=1;i<=qn;i++) { scanf("%d%d%d",&opt,&x,&y); if(opt==0) c[++ccnt]=mdf{x,y}; else q[++qcnt]=qry{x,y,0,ccnt,qcnt}; } n=0; dfs(1,0);len=pow(n,0.666); for(int k=1;k<=20;k++) for(int i=1;i<=n/2;i++) f[k][i]=f[k-1][f[k-1][i]]; for(int i=1;i<=n;i++) bel[i]=(i-1)/len+1; for(int i=1;i<=qcnt;i++) { if(ll[q[i].l]>ll[q[i].r]) swap(q[i].l,q[i].r); q[i].lca=getlca(q[i].l,q[i].r); if(q[i].lca==q[i].l) { q[i].lca=0; q[i].l=ll[q[i].l];q[i].r=ll[q[i].r]; } else { q[i].lca=ll[q[i].lca]; q[i].l=rr[q[i].l];q[i].r=ll[q[i].r]; } } sort(q+1,q+1+qcnt,cmp); } inline long long solv(int i) { vis[idx[i]]^=1; if(vis[idx[i]]) return val[a[idx[i]]]*w[++num[a[idx[i]]]]; else return -val[a[idx[i]]]*w[num[a[idx[i]]]--]; } inline void mainwork() { long long now=0;int l=1,r=0,t=0; for(int i=1;i<=qcnt;i++) { while(r<q[i].r) ++r,now+=solv(r); while(l>q[i].l) --l,now+=solv(l); while(r>q[i].r) now+=solv(r),--r; while(l<q[i].l) now+=solv(l),++l; while(t<q[i].t) { ++t; if(q[i].l<=ll[c[t].pos] && ll[c[t].pos]<=q[i].r) now+=solv(ll[c[t].pos]); if(q[i].l<=rr[c[t].pos] && rr[c[t].pos]<=q[i].r) now+=solv(rr[c[t].pos]); swap(c[t].col,a[c[t].pos]); if(q[i].l<=ll[c[t].pos] && ll[c[t].pos]<=q[i].r) now+=solv(ll[c[t].pos]); if(q[i].l<=rr[c[t].pos] && rr[c[t].pos]<=q[i].r) now+=solv(rr[c[t].pos]); } while(t>q[i].t) { if(q[i].l<=ll[c[t].pos] && ll[c[t].pos]<=q[i].r) now+=solv(ll[c[t].pos]); if(q[i].l<=rr[c[t].pos] && rr[c[t].pos]<=q[i].r) now+=solv(rr[c[t].pos]); swap(c[t].col,a[c[t].pos]); if(q[i].l<=ll[c[t].pos] && ll[c[t].pos]<=q[i].r) now+=solv(ll[c[t].pos]); if(q[i].l<=rr[c[t].pos] && rr[c[t].pos]<=q[i].r) now+=solv(rr[c[t].pos]); t--; } if(q[i].lca) now+=solv(q[i].lca); ans[q[i].id]=now; if(q[i].lca) now+=solv(q[i].lca); } } inline void print() { for(int i=1;i<=qcnt;i++) printf("%lld\n",ans[i]); } int main() { prework(); mainwork(); print(); return 0; }
