學到了新姿勢，splay維護括號序列（聽說是偽ETT(euler-tour-tree 歐拉搜索樹)？）

大型工業題

注意點：1：結構改變了以后編號變成不連續的了，要找前驅和后繼

2:就算lazy也需要先把當前點改了，不然計算出鍋

#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; typedef long long LL; struct trnode {int f,son[2];LL c,ptt,d,sum,lazy; }tr[210000]; void update(int now) {int lc=tr[now].son[0],rc=tr[now].son[1];tr[now].ptt=tr[now].c+tr[lc].ptt+tr[rc].ptt;tr[now].sum=tr[now].d+tr[lc].sum+tr[rc].sum; } void rotate(int x,int w) {int f=tr[x].f,ff=tr[f].f;int R,r;R=f,r=tr[x].son[w];tr[R].son[1-w]=r;if(r!=0)tr[r].f=R;R=ff,r=x;if(tr[ff].son[0]==f)tr[R].son[0]=r;else tr[R].son[1]=r;tr[r].f=R;R=x,r=f;tr[R].son[w]=r;tr[r].f=R;update(f);update(x); } void pushdown(int x) {int k=tr[x].lazy;tr[x].lazy=0;int lc=tr[x].son[0],rc=tr[x].son[1];if(lc!=0){tr[lc].lazy+=k;tr[lc].d+=tr[lc].c*k;tr[lc].sum+=tr[lc].ptt*k;}if(rc!=0){tr[rc].lazy+=k;tr[rc].d+=tr[rc].c*k;tr[rc].sum+=tr[rc].ptt*k;} } int tt,tmp[210000]; void splay(int x,int rt) {int i=x; tt=0;while(i!=rt)tmp[++tt]=i,i=tr[i].f;while(tt>0){ if(tr[tmp[tt]].lazy!=0)pushdown(tmp[tt]); tt--;}while(tr[x].f!=rt){int f=tr[x].f,ff=tr[f].f;if(ff==rt){if(tr[f].son[0]==x)rotate(x,1);else rotate(x,0);}else{if(tr[ff].son[0]==f&&tr[f].son[0]==x)rotate(f,1),rotate(x,1);else if(tr[ff].son[1]==f&&tr[f].son[1]==x)rotate(f,0),rotate(x,0);else if(tr[ff].son[0]==f&&tr[f].son[1]==x)rotate(x,0),rotate(x,1);else if(tr[ff].son[1]==f&&tr[f].son[0]==x)rotate(x,1),rotate(x,0);}} } //~~~~~~~~~~~~~~~base~~~~~~~~~~~~~~~int tp; void insert(int now,int d,int c,int f,int w) {if(now==1||now==tp)c=0;tr[now].f=f;tr[now].son[0]=tr[now].son[1]=0;tr[now].c=tr[now].ptt=c;tr[now].d=tr[now].sum=d;tr[now].lazy=0;if(f!=0)tr[f].son[w]=now; } void cut(int x) {int f=tr[x].f; tr[x].f=0;if(tr[f].son[0]==x)tr[f].son[0]=0;else tr[f].son[1]=0;splay(f,0); } int findL(int x){while(tr[x].son[0]!=0)x=tr[x].son[0]; return x;} int findR(int x){while(tr[x].son[1]!=0)x=tr[x].son[1]; return x;} int findqq(int x){splay(x,0);x=tr[x].son[0]; return findR(x);} int findhj(int x){splay(x,0);x=tr[x].son[1]; return findL(x);} //~~~~~~~~~~~~~~~in~~~~~~~~~~~~~~~~~ LL c[210000]; int list[210000],uz[210000];//按dfs序把樹上的點取出 int yL[210000],yR[210000];//第i個點的左右括號的樹上編號 void maketree(int l,int r,int f,int w) {if(l>r)return ;int mid=(l+r)/2;int x=list[mid],u=uz[mid],now=u>0?yL[x]:yR[x];insert(now,c[x]*u,u,f,w);maketree(l,mid-1,now,0);maketree(mid+1,r,now,1);update(now); } LL getsum(int x) {x=findhj(x);splay(x,0);return tr[tr[x].son[0]].sum; } void move(int l,int r,int p) {int ll=findqq(l),rr=findhj(r);splay(ll,0),splay(rr,ll);int x=tr[rr].son[0];cut(x);splay(p,0);int y=tr[p].son[1];cut(y);tr[x].f=p,tr[p].son[1]=x;rr=findR(x);splay(rr,0);tr[y].f=rr,tr[rr].son[1]=y;splay(y,0); } void change(int l,int r,int k) {int ll=findqq(l),rr=findhj(r);splay(ll,0),splay(rr,ll);int x=tr[rr].son[0];tr[x].lazy+=k;tr[x].d+=tr[x].c*k;tr[x].sum+=tr[x].ptt*k;} //~~~~~~~~~~out~~~~~~~~~~~~~~~~~~//---------------------------------------ETT----------------------------------------------------struct node {int x,y,next; }a[110000];int len,last[110000]; void ins(int x,int y) {len++;a[len].x=x;a[len].y=y;a[len].next=last[x];last[x]=len; } void dfs(int x) {list[++tp]=x;uz[tp]=1;yL[x]=tp; for(int k=last[x];k;k=a[k].next)dfs(a[k].y);list[++tp]=x;uz[tp]=-1;yR[x]=tp; }char ss[10]; int main() {freopen("a.in","r",stdin);freopen("a.out","w",stdout);int n,F;scanf("%d",&n);len=0;memset(last,0,sizeof(last));for(int i=2;i<=n;i++)scanf("%d",&F), ins(F,i);for(int i=1;i<=n;i++)scanf("%d",&c[i]); tp=0;list[++tp]=0;uz[tp]=1;yL[0]=tp;dfs(1);list[++tp]=0;uz[tp]=-1;yR[0]=tp; maketree(1,tp,0,0);int Q,x,y;scanf("%d",&Q);while(Q--){scanf("%s",ss+1);if(ss[1]=='Q'){scanf("%d",&x);printf("%lld\n",getsum(yL[x]));}else if(ss[1]=='C'){scanf("%d%d",&x,&y);move(yL[x],yR[x],yL[y]);}else{scanf("%d%d",&x,&y);change(yL[x],yR[x],y);}}return 0; }

?

轉載于:https://www.cnblogs.com/AKCqhzdy/p/10201937.html

總結

以上是生活随笔為你收集整理的bzoj3786: 星系探索的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。