BZOJ3786: 星系探索（伪ETT）

雨点打透心脏的1/2处 2021-12-23 05:47 99阅读 0赞

## 题面 ##

[传送门][Link 1]

## 题解 ##

坑啊……我好像把\\(Splay\\)的东西全忘光了……

\\(ETT\\)（\\(Euler\\ Tour\\ Tree\\)）是一种可以资瓷比\\(LCT\\)更多功能的数据结构，然而不管是功能还是复杂度都远远比不上\\(TopTree\\)和\\(LCT\\)（然而我似乎连\\(TopTree\\)都不会……）

然而一般情况下我们需要用到的只有伪\\(ETT\\)，用人话说就是用\\(Splay\\)维护欧拉序，进栈的时候值为\\(+v\\)，出栈的时候值为\\(-v\\)，那么\\(1\\)到\\(u\\)的路径上的所有数之和就是\\(dfs\\)序上\\(ls\[1\]\\)到\\(ls\[u\]\\)的所有数之和了（虽然看别的大佬的博客说这东西资瓷查询任意两点间路径和……然而咱并不明白该怎么搞……如果有知道的可以在下面告诉咱一声么qwq）

换根操作的话，就相当于提出一个区间放到另一个地方，\\(Splay\\)一下就好了

//minamoto #include<bits/stdc++.h> #define R register #define ll long long #define inline __inline__ __attribute__((always_inline)) #define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i) #define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i) #define go(u) for(int i=head[u],v=E[i].v;i;i=E[i].nx,v=E[i].v) using namespace std; char buf[1<<21],*p1=buf,*p2=buf; inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;} int read(){ R int res,f=1;R char ch; while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1); for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0'); return res*f; } inline char getop(){R char ch;while((ch=getc())>'Z'||ch<'A');return ch;} char sr[1<<21],z[20];int C=-1,Z=0; inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;} void print(R ll x){ if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x; while(z[++Z]=x%10+48,x/=10); while(sr[++C]=z[Z],--Z);sr[++C]='\n'; } const int N=2e5+5; struct eg{int v,nx;}E[N];int head[N],tot; inline void add(R int u,R int v){E[++tot]={v,head[u]},head[u]=tot;} struct node;typedef node* ptr; struct node{ ptr fa,lc,rc;int sz,ty;ll sum,t,v; inline node(); inline void init(R int x,R int s){sz=ty=s,v=sum=x;} inline void ppd(R ll x){sum+=x*sz,v+=x*ty,t+=x;} inline void pd(){if(t)lc->ppd(t),rc->ppd(t),t=0;} inline ptr upd(){sum=lc->sum+rc->sum+v,sz=lc->sz+rc->sz+ty;return this;} }e[N],*rt; inline node::node(){lc=rc=fa=e;} void push(ptr rt,ptr p){if(p!=rt)push(rt,p->fa);p->pd();} void rotate(ptr &rt,ptr p){ ptr s=p->fa,t=s->fa; if(s!=rt)(t->lc==s?t->lc:t->rc)=p;else rt=p; p->fa=t,s->fa=p; if(s->lc==p)s->lc=p->rc,p->rc->fa=s,p->rc=s->upd(); else s->rc=p->lc,p->lc->fa=s,p->lc=s->upd(); } ptr splay(ptr &rt,ptr p){ push(rt,p); while(p!=rt){ if(p->fa!=rt)rotate(rt,p->fa->lc==p^p->fa->fa->lc==p->fa?p:p->fa); rotate(rt,p); } return p->upd(); } inline ptr lst(ptr p){p=splay(rt,p)->lc;while(p->rc!=e)p=p->rc;return p;} inline ptr nxt(ptr p){p=splay(rt,p)->rc;while(p->lc!=e)p=p->lc;return p;} inline ptr split(ptr s,ptr t){s=lst(s),t=nxt(t),splay(rt,s);return splay(s->rc,t);} int a[N],val[N],ls[N],rs[N],tim; void dfs(int u){ ls[u]=++tim,val[tim]=u; go(u)dfs(v); rs[u]=++tim,val[tim]=-u; } void build(ptr &p,int l,int r,ptr fa){ int mid=(l+r)>>1;p=e+mid,p->fa=fa; val[mid]>0?p->init(a[val[mid]],1):p->init(-a[-val[mid]],-1); if(l<mid)build(p->lc,l,mid-1,p); if(mid<r)build(p->rc,mid+1,r,p); p->upd(); } inline ll get(R int x){return split(e+ls[1],e+ls[x])->lc->sum;} void move(int x,int y){ ptr s=split(e+ls[x],e+rs[x]),t=s->lc; s->lc=t->fa=e,s->upd(),s->fa->upd(); splay(rt,e+ls[y]),s=splay(rt->rc,nxt(rt)); s->lc=t,t->fa=s,s->upd(),s->fa->upd(); } void tag(int x,int y){split(e+ls[x],e+rs[x])->lc->ppd(y);} int n,m; int main(){ // freopen("testdata.in","r",stdin); n=read(); for(R int i=2,x;i<=n;++i)x=read(),add(x,i); fp(i,1,n)a[i]=read(); tim=1,dfs(1),build(rt,1,tim+1,e); m=read(); char op;int x,y; while(m--){ op=getop(),x=read(); switch(op){ case 'Q':print(get(x));break; case 'C':y=read(),move(x,y);break; case 'F':y=read(),tag(x,y);break; } } return Ot(),0; }

转载于:https://www.cnblogs.com/bztMinamoto/p/10715071.html

[Link 1]: https://www.lydsy.com/JudgeOnline/problem.php?id=3786