爱魔域

1 sec 512MB

题意：

给你一颗\(n\)个点，魔域口袋世界boos怎么打初始点权为\(0\)的有跟树，要求支持

Increase x y w 将路径\(x\)到\(y\)所有点点权加上\(w\)

Sum x y 询问路径\(x\)到\(y\)的点权和

Major x y 询问从路径\(x\)到\(y\)最大点权

Minor x y 询问最小点权

Invert x y 将路径上的点权翻转

有个性质，修改操作一定满足\(x\)为\(y\)祖先或者\(y\)为\(x\)祖先（实际没什么用处）

\(n\le 50000,|w|\le 1000\)

输入格式

第一行有三个整数\(N\)、\(M\)和\(R\)，分别表示树的节点数、指令和询问总数，以及树的跟。

接下来\(N-1\)行，每行两个整数\(u\)和\(v\)，表示一条边。

接下来\(M\)行，每行描述一个指令或询问，格式见题意描述。

输出格式

对于每个询问操作，输出所求的值。

老年菜鸡选手实在写不动大数据结构题...

有两个做法，暂时只写了一种，有可能一会儿会把另一种补充一下。

考虑树链剖分，但是不能维护翻转

考虑平衡树可以维护翻转

于是我们可以拿平衡树维护树剖的每条链

然后每次修改只有\(\log\)条链，我们把每条链要修改的地方拎出来，然后塞到一个平衡树里面，打一个翻转tag，再塞回去就可以了

用fhqtreap实现起来比较方便

说起来蛮简单，写起来还是蛮难受的的

Code:

#include <cstdio> #include <cctype> #include <cstdlib> #include <algorithm> #define ll long long const int SIZE=1<<21; char ibuf[SIZE],*iS,*iT; //#define gc() (iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,SIZE,stdin),iS==iT?EOF:*iS++):*iS++) #define gc() getchar() template <class T> void read(T &x) { int f=0;x=0;char c=gc(); while(!isdigit(c)) f|=c=='-',c=gc(); while(isdigit(c)) x=x*10+c-'0',c=gc(); if(f) x=-x; } void reads(char *s) { int k=0;char c=gc(); while(c<'A'||c>'Z') c=gc(); while((c>='a'&&c<='z')||(c>='A'&&c<='Z')) s[k++]=c,c=gc(); } const int N=5e4+10; inline void ckmax(int &x,int y){x=x>y?x:y;} inline void ckmin(int &x,int y){x=x<y?x:y;} int n,m,r,root[N]; namespace treap { int ch[N][2],mx[N],mi[N],siz[N],val[N],dat[N],tag[N],reve[N],tot; ll sum[N]; #define ls ch[now][0] #define rs ch[now][1] void updata(int now) { sum[now]=sum[ls]+dat[now]+sum[rs]; siz[now]=siz[ls]+1+siz[rs]; mx[now]=mi[now]=dat[now]; if(ls) { ckmax(mx[now],mx[ls]); ckmin(mi[now],mi[ls]); } if(rs) { ckmax(mx[now],mx[rs]); ckmin(mi[now],mi[rs]); } } void Reverse(int now) { std::swap(ls,rs),reve[now]^=1; } void upt(int now,int d) { dat[now]+=d; tag[now]+=d; mi[now]+=d; mx[now]+=d; sum[now]+=d*siz[now]; } void pushdown(int now) { if(reve[now]) { if(ls) Reverse(ls); if(rs) Reverse(rs); reve[now]=0; } if(tag[now]) { if(ls) upt(ls,tag[now]); if(rs) upt(rs,tag[now]); tag[now]=0; } } void split(int now,int &x,int &y,int k) { if(!now){x=y=0;return;} pushdown(now); if(k<=siz[ls]) y=now,split(ls,x,ch[y][0],k); else x=now,split(rs,ch[x][1],y,k-siz[ls]-1); updata(now); } int Merge(int x,int y) { if(!x||!y) return x^y; pushdown(x),pushdown(y); if(val[x]<val[y]) { ch[x][1]=Merge(ch[x][1],y); updata(x); return x; } else { ch[y][0]=Merge(x,ch[y][0]); updata(y); return y; } } int New(int d) { val[++tot]=rand(),siz[tot]=1,sum[tot]=mi[tot]=mx[tot]=dat[tot]=d; return tot; } void ins(int id,int d) { root[id]=Merge(root[id],New(d)); } ll querysum(int id,int l,int r) { int x,y,z; split(root[id],x,y,r); split(x,x,z,l-1); ll ret=sum[z]; root[id]=Merge(x,Merge(z,y)); return ret; } int querymi(int id,int l,int r) { int x,y,z; split(root[id],x,y,r); split(x,x,z,l-1); int ret=mi[z]; root[id]=Merge(x,Merge(z,y)); return ret; } int querymx(int id,int l,int r) { int x,y,z; split(root[id],x,y,r); split(x,x,z,l-1); int ret=mx[z]; root[id]=Merge(x,Merge(z,y)); return ret; } void modify(int id,int l,int r,int w) { int x,y,z; split(root[id],x,y,r); split(x,x,z,l-1); upt(z,w); root[id]=Merge(x,Merge(z,y)); } } using treap::modify; using treap::querysum; using treap::querymi; using treap::querymx; using treap::ins; using treap::Merge; using treap::split; using treap::Reverse; int head[N],to[N<<1],Next[N<<1],cnt; void add(int u,int v) { to[++cnt]=v,Next[cnt]=head[u],head[u]=cnt; } int top[N],ws[N],siz[N],par[N],dep[N],rk[N],num[N]; void dfs(int now) { siz[now]=1; dep[now]=dep[par[now]]+1; for(int v,i=head[now];i;i=Next[i]) if((v=to[i])!=par[now]) { par[v]=now; dfs(v); siz[now]+=siz[v]; if(siz[ws[now]]<siz[v]) ws[now]=v; } } int lin,tot[N]; void dfs(int now,int id,int anc) { top[now]=anc; num[now]=id; rk[now]=++tot[id]; ins(id,0); if(ws[now]) dfs(ws[now],id,anc); for(int v,i=head[now];i;i=Next[i]) if(!num[v=to[i]]) dfs(v,++lin,v); } void modi(int x,int y,int w) { if(dep[x]<dep[y]) std::swap(x,y); while(top[x]!=top[y]) { modify(num[x],1,rk[x],w); x=par[top[x]]; } if(dep[x]<dep[y]) std::swap(x,y); modify(num[x],rk[y],rk[x],w); } void qrysum(int x,int y) { ll ret=0; while(top[x]!=top[y]) { if(dep[top[x]]>dep[top[y]]) { ret+=querysum(num[x],1,rk[x]); x=par[top[x]]; } else { ret+=querysum(num[y],1,rk[y]); y=par[top[y]]; } } if(dep[x]<dep[y]) std::swap(x,y); ret+=querysum(num[x],rk[y],rk[x]); printf("%lld\n",ret); } void qrymx(int x,int y) { int ret=-(1<<30); while(top[x]!=top[y]) { if(dep[top[x]]>dep[top[y]]) { ckmax(ret,querymx(num[x],1,rk[x])); x=par[top[x]]; } else { ckmax(ret,querymx(num[y],1,rk[y])); y=par[top[y]]; } } if(dep[x]<dep[y]) std::swap(x,y); ckmax(ret,querymx(num[x],rk[y],rk[x])); printf("%d\n",ret); } void qrymi(int x,int y) { int ret=1<<30; while(top[x]!=top[y]) { if(dep[top[x]]>dep[top[y]]) { ckmin(ret,querymi(num[x],1,rk[x])); x=par[top[x]]; } else { ckmin(ret,querymi(num[y],1,rk[y])); y=par[top[y]]; } } if(dep[x]<dep[y]) std::swap(x,y); ckmin(ret,querymi(num[x],rk[y],rk[x])); printf("%d\n",ret); } void rev(int x,int y) { int tx=x,ty=y; if(dep[x]<dep[y]) std::swap(x,y); int rt=0; while(top[x]!=top[y]) { int id=num[x],k=rk[x],pre; split(root[id],pre,root[id],k); rt=Merge(pre,rt); x=par[top[x]]; } if(dep[x]<dep[y]) std::swap(x,y); int id=num[x],l=rk[y],r=rk[x],a,b,c; split(root[id],a,c,r); split(a,a,b,l-1); rt=Merge(b,rt); Reverse(rt); x=tx,y=ty; if(dep[x]<dep[y]) std::swap(x,y); while(top[x]!=top[y]) { int id=num[x],k=rk[x],pre; split(rt,rt,pre,treap::siz[rt]-k); root[id]=Merge(pre,root[id]); x=par[top[x]]; } id=num[x]; root[id]=Merge(a,Merge(rt,c)); } int main() { //freopen("data.in","r",stdin); //freopen("data.out","w",stdout); read(n),read(m),read(r); for(int u,v,i=1;i<n;i++) read(u),read(v),add(u,v),add(v,u); dfs(r); dfs(r,++lin,r); char op[23]; for(int x,y,w,i=1;i<=m;i++) { reads(op),read(x),read(y); if(op[0]=='I') { if(op[2]=='c') read(w),modi(x,y,w); else rev(x,y); } else if(op[0]=='S') qrysum(x,y); else { if(op[1]=='a') qrymx(x,y); else qrymi(x,y); } } return 0; }

2019.5.22