【bzoj 3786】星系探索

Description

物理学家小C的研究正遇到某个瓶颈。

他正在研究的是一个星系，这个星系中有n个星球，其中有一个主星球（方便起见我们默认其为1号星球），其余的所有星球均有且仅有一个依赖星球。主星球没有依赖星球。

我们定义依赖关系如下：若星球a的依赖星球是b，则有星球a依赖星球b。此外，依赖关系具有传递性，即若星球a依赖星球b，星球b依赖星球c，则有星球a依赖星球c。

对于这个神秘的星系中，小C初步探究了它的性质，发现星球之间的依赖关系是无环的。并且从星球a出发只能直接到达它的依赖星球b。

每个星球i都有一个能量系数wi。小C想进行若干次实验，第i次实验，他将从飞船上向星球di发射一个初始能量为0的能量收集器，能量收集器会从星球di开始前往主星球，并收集沿途每个星球的部分能量，收集能量的多少等于这个星球的能量系数。

但是星系的构成并不是一成不变的，某些时刻，星系可能由于某些复杂的原因发生变化。

有些时刻，某个星球能量激发，将使得所有依赖于它的星球以及他自己的能量系数均增加一个定值。还有可能在某些时刻，某个星球的依赖星球会发生变化，但变化后依然满足依赖关系是无环的。

现在小C已经测定了时刻0时每个星球的能量系数，以及每个星球(除了主星球之外)的依赖星球。接下来的m个时刻，每个时刻都会发生一些事件。其中小C可能会进行若干次实验，对于他的每一次实验，请你告诉他这一次实验能量收集器的最终能量是多少。

Input

第一行一个整数n，表示星系的星球数。

接下来n-1行每行一个整数,分别表示星球2-n的依赖星球编号。

接下来一行n个整数，表示每个星球在时刻0时的初始能量系数wi。

接下来一行一个整数m，表示事件的总数。

事件分为以下三种类型。

(1)"Q di"表示小C要开始一次实验,收集器的初始位置在星球di。

(2)"C xi yi"表示星球xi的依赖星球变为了星球yi。

(3)"F pi qi"表示星球pi能量激发，常数为qi。

Output

对于每一个事件类型为Q的事件，输出一行一个整数，表示此次实验的收集器最终能量。

Sample Input

3
1
1
4 5 7
5
Q 2
F 1 3
Q 2
C 2 3
Q 2

Sample Output

9
15
25

HINT

n<=100000,m<=300000,1<di,xi<=n,wi,qi<=100000.保证操作合法。注意w_i>=0。

纪念一下一道调了两天发现自己忘开long long的题>_<

简单地写一下题解吧。

首先，为了将子树变成一段连续的区间，我们需要将每个点拆成两个，一个代表入栈，一个代表出栈。入栈时点权为正，出栈时为负，这样一个点到根节点的路径上的点权和等于前缀和。先在整棵树上dfs，把这些点塞进一个队列里，根据队列把树建好，然后就是疯狂地拆拆拆和splay。

fhq-treap分裂过程中记录父亲【Time:32912ms】（因为多了一个find函数还需要记一下父亲）

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<cstdlib>

 #define LL long long

 using namespace std;

 const int N=2e5+;

 int n,m,cnt,tmp,x,y,root,rt1,rt2,rt3;

 int st[N],q[N],first[N],ch[N][];

 LL sh[N][];

 char op[];

 struct edge{int to,next;}e[N];

 #define lc ch][0

 #define rc ch][1

 #define rnd ch][2

 #define sz ch][3

 #define xi ch][4

 #define num ch][5

 #define fa ch][6

 #define v sh][0

 #define sum sh][1

 #define tag sh][2

 int read()

 {

     int x=,f=;char c=getchar();

     while(c<''||c>''){if(c=='-')f=-;c=getchar();}

     while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

     return x*f;

 }

 void ins(int from,int to){e[++cnt]=(edge){to,first[from]};first[from]=cnt;}

 void dfs(int x)

 {

     q[++cnt]=x;

     for(int i=first[x];i;i=e[i].next)dfs(e[i].to);

     q[++cnt]=x+n;

 }

 void up(int w)

 {

     int l=w[lc],r=w[rc];

     w[sz]=l[sz]+r[sz]+;

     w[num]=l[num]+r[num]+w[xi];

     w[sum]=l[sum]+r[sum]+w[v];

 }

 void dn(int w)

 {

     int l=w[lc],r=w[rc];LL t=w[tag];

     if(!t)return;w[tag]=;

     if(l)l[tag]+=t,l[v]+=t*l[xi],l[sum]+=t*l[num];

     if(r)r[tag]+=t,r[v]+=t*r[xi],r[sum]+=t*r[num];

 //    printf("l:%d xi:%d r:%d xi:%d\n",l,l[xi],r,r[xi]);

 }

 void check(int w){if(!w)return;check(w[lc]);check(w[rc]);up(w);}

 int build(int n)

 {

     int top=,w;

     for(int i=;i<=n;i++)

     {

         w=q[i];w[rnd]=rand();

         while(top&&st[top][rnd]>w[rnd])

         {

             w[lc][fa]=st[top];st[top][rc]=w[lc];

             st[top][fa]=w;w[lc]=st[top--];

         }

         w[fa]=st[top];st[top][rc]=w;st[++top]=w;

     }

     ch[][]=;st[][fa]=;check(st[]);

     return st[];

 }

 void split(int w,int& l,int fal,int& r,int far,int k)

 {

     if(!w){l=r=;return;}

     dn(w);int lson=w[lc][sz];

     if(k<=lson)w[fa]=far,r=w,split(w[lc],l,fal,w[lc],w,k);

     else w[fa]=fal,l=w,split(w[rc],w[rc],w,r,far,k-lson-);

     up(w);

 }

 int merge(int a,int b)

 {

     if(!a||!b)return a+b;

     if(a[rnd]<b[rnd]){dn(a);a[rc]=merge(a[rc],b);a[rc][fa]=a;up(a);return a;}

     else {dn(b);b[lc]=merge(a,b[lc]);b[lc][fa]=b;up(b);return b;}

 }

 int find(int x)

 {

     int ans=x[lc][sz]+;

     while(x[fa])

     {

         if(x[fa][rc]==x)ans+=x[fa][lc][sz]+;

         x=x[fa];

     }

     return ans;

 }

 void query()

 {

     x=read();rt1=rt2=;split(root,rt1,,rt2,,find(x));

     printf("%lld\n",rt1[sum]);root=merge(rt1,rt2);

 }

 void change()

 {

     x=read();y=read();rt1=rt2=rt3=;

     split(root,rt1,,rt3,,find(x+n));

     root=rt1;rt1=;split(root,rt1,,rt2,,find(x)-);

     root=merge(rt1,rt3);rt1=rt3=;

     split(root,rt1,,rt3,,find(y));

     root=merge(rt1,rt2);root=merge(root,rt3);

 }

 void add()

 {

     x=read();y=read();rt1=rt2=rt3=;

     split(root,rt1,,rt3,,find(x+n));

     root=rt1;rt1=;split(root,rt1,,rt2,,find(x)-);

     int w=rt2;w[tag]+=y;w[v]+=y*w[xi];w[sum]+=1ll*y*w[num];

     root=merge(rt1,rt2);root=merge(root,rt3);

 }

 void print(int w,int dir)

 {

     if(!w)return;

     if(dir==)printf("from-left ");

     if(dir==)printf("from-right ");

     printf("[%d] fa:%d v:%lld sum:%lld lson:%d rson:%d\n",w,w[fa],w[v],w[sum],w[lc],w[rc]);

     print(w[lc],);print(w[rc],);

 }

 int main()

 {

     n=read();

     for(int i=;i<=n;i++)tmp=read(),ins(tmp,i);

     for(int i=;i<=n;i++)tmp=read(),i[v]=tmp,(i+n)[v]=-tmp,i[xi]=,(i+n)[xi]=-;

     cnt=;dfs();root=build(n*);m=read();//print(root,-1);

     while(m--)

     {

         scanf("%s",op+);

         if(op[]=='Q')query();

         else if(op[]=='C')change();

         else add();

 //        print(root,-1);

     }

     return ;

 }

fhq-treap up时更新父亲【Time:37452ms】（分裂出来的根节点的父亲记得清零）

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<cstdlib>

 #define LL long long

 using namespace std;

 const int N=2e5+;

 int n,m,cnt,tmp,x,y,root,rt1,rt2,rt3;

 int st[N],q[N],first[N],ch[N][];

 LL sh[N][];

 char op[];

 struct edge{int to,next;}e[N];

 #define lc ch][0

 #define rc ch][1

 #define rnd ch][2

 #define sz ch][3

 #define xi ch][4

 #define num ch][5

 #define fa ch][6

 #define v sh][0

 #define sum sh][1

 #define tag sh][2

 int read()

 {

     int x=,f=;char c=getchar();

     while(c<''||c>''){if(c=='-')f=-;c=getchar();}

     while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

     return x*f;

 }

 void ins(int from,int to){e[++cnt]=(edge){to,first[from]};first[from]=cnt;}

 void dfs(int x)

 {

     q[++cnt]=x;

     for(int i=first[x];i;i=e[i].next)dfs(e[i].to);

     q[++cnt]=x+n;

 }

 void up(int w)

 {

     int l=w[lc],r=w[rc];

     w[sz]=l[sz]+r[sz]+;

     w[num]=l[num]+r[num]+w[xi];

     w[sum]=l[sum]+r[sum]+w[v];

     if(l)l[fa]=w;if(r)r[fa]=w;

 }

 void dn(int w)

 {

     int l=w[lc],r=w[rc];LL t=w[tag];

     if(!t)return;w[tag]=;

     if(l)l[tag]+=t,l[v]+=t*l[xi],l[sum]+=t*l[num];

     if(r)r[tag]+=t,r[v]+=t*r[xi],r[sum]+=t*r[num];

 }

 void check(int w){if(!w)return;check(w[lc]);check(w[rc]);up(w);}

 int build(int n)

 {

     int top=,w;

     for(int i=;i<=n;i++)

     {

         w=q[i];w[rnd]=rand();

         while(top&&st[top][rnd]>w[rnd])st[top][rc]=w[lc],w[lc]=st[top--];

         st[top][rc]=w;st[++top]=w;

     }

     ch[][]=;st[][fa]=;check(st[]);

     return st[];

 }

 void split(int w,int& l,int fal,int& r,int far,int k)

 {

     if(!w){l=r=;return;}

     dn(w);int lson=w[lc][sz];

     if(k<=lson)r=w,split(w[lc],l,fal,w[lc],w,k);

     else l=w,split(w[rc],w[rc],w,r,far,k-lson-);

     up(w);

 }

 int merge(int a,int b)

 {

     if(!a||!b)return a+b;

     if(a[rnd]<b[rnd]){dn(a);a[rc]=merge(a[rc],b);up(a);return a;}

     else {dn(b);b[lc]=merge(a,b[lc]);up(b);return b;}

 }

 int find(int x)

 {

     int ans=x[lc][sz]+;

     while(x[fa])

     {

         if(x[fa][rc]==x)ans+=x[fa][lc][sz]+;

         x=x[fa];

     }

     return ans;

 }

 void query()

 {

     x=read();rt1=rt2=;split(root,rt1,,rt2,,find(x));

     rt1[fa]=rt2[fa]=;printf("%lld\n",rt1[sum]);root=merge(rt1,rt2);root[fa]=;

 }

 void change()

 {

     x=read();y=read();rt1=rt2=rt3=;

     split(root,rt1,,rt3,,find(x+n));

     rt1[fa]=rt3[fa]=;root=rt1;rt1=;

     split(root,rt1,,rt2,,find(x)-);

     rt1[fa]=rt2[fa]=;root=merge(rt1,rt3);rt1=rt3=;

     split(root,rt1,,rt3,,find(y));

     root=merge(rt1,rt2);root=merge(root,rt3);root[fa]=;

 }

 void add()

 {

     x=read();y=read();rt1=rt2=rt3=;

     split(root,rt1,,rt3,,find(x+n));

     rt1[fa]=rt3[fa]=;root=rt1;rt1=;

     split(root,rt1,,rt2,,find(x)-);rt1[fa]=rt2[fa]=;

     int w=rt2;w[tag]+=y;w[v]+=y*w[xi];w[sum]+=1ll*y*w[num];

     root=merge(rt1,rt2);root=merge(root,rt3);root[fa]=;

 }

 int main()

 {

     n=read();

     for(int i=;i<=n;i++)tmp=read(),ins(tmp,i);

     for(int i=;i<=n;i++)tmp=read(),i[v]=tmp,(i+n)[v]=-tmp,i[xi]=,(i+n)[xi]=-;

     cnt=;dfs();

     root=build(n*);m=read();

     while(m--)

     {

         scanf("%s",op+);

         if(op[]=='Q')query();

         else if(op[]=='C')change();

         else add();

     }

     return ;

 }

splay直接查找前驱后继【Time:25484 ms】（数组版仿佛很容易TLE……慎重）

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 const int inf=0x3f3f3f3f;

 const int N=;

 struct node{int ch[],size,fa,t,num;long long v,sum,tag;}tr[N<<];

 struct edge{int next,to;}e[N];

 int n,m,f,root,cnt;

 int head[N],q[N<<],s[N];

 int read()

 {

     int x=,f=;char c=getchar();

     while(c<''||c>''){if(c=='-')f=-;c=getchar();}

     while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

     return x*f;

 }

 void insert(int a,int b){cnt++;e[cnt].to=b;e[cnt].next=head[a];head[a]=cnt;}

 void dfs(int x)

 {

     q[++cnt]=x+;

     for(int i=head[x];i;i=e[i].next)dfs(e[i].to);

     q[++cnt]=x+n+;

 }

 void pushup(int x)

 {

     int l=tr[x].ch[],r=tr[x].ch[];

     tr[x].size=tr[l].size+tr[r].size+;

     tr[x].num=tr[l].num+tr[r].num+tr[x].t;

     tr[x].sum=tr[l].sum+tr[r].sum+tr[x].v;

 }

 void pushdown(int x)

 {

     int l=tr[x].ch[],r=tr[x].ch[];long long tag=tr[x].tag;

     if(l)tr[l].tag+=tag,tr[l].sum+=tag*tr[l].num,tr[l].v+=tag*tr[l].t;

     if(r)tr[r].tag+=tag,tr[r].sum+=tag*tr[r].num,tr[r].v+=tag*tr[r].t;

     tr[x].tag=;

 }

 void rotate(int x,int& k)

 {

     int y=tr[x].fa,z=tr[y].fa,l,r;

     if(tr[y].ch[]==x)l=;else l=;r=l^;

     if(y==k)k=x;

     else{if(tr[z].ch[]==y)tr[z].ch[]=x;else tr[z].ch[]=x;}

     tr[x].fa=z;tr[y].fa=x;tr[tr[x].ch[r]].fa=y;

     tr[y].ch[l]=tr[x].ch[r];tr[x].ch[r]=y;

     pushup(y);pushup(x);

 }

 void splay(int x,int& k)

 {

     int top=;s[++top]=x;

     for(int i=x;tr[i].fa;i=tr[i].fa)s[++top]=tr[i].fa;

     for(int i=top;i;i--)if(tr[s[i]].tag)pushdown(s[i]);

     while(x!=k)

     {

         int y=tr[x].fa,z=tr[y].fa;

         if(y!=k)

         {

             if((tr[y].ch[]==x)^(tr[z].ch[]==y))rotate(x,k);

             else rotate(y,k);

         }

         rotate(x,k);

     }

 }

 int fmin(int x){while(tr[x].ch[])x=tr[x].ch[];return x;}

 int fmax(int x){while(tr[x].ch[])x=tr[x].ch[];return x;}

 void split(int l,int r)

 {

     splay(l,root);int x=fmax(tr[l].ch[]);

     splay(r,root);int y=fmin(tr[r].ch[]);

     splay(x,root);splay(y,tr[x].ch[]);

 }

 void build(int l,int r,int last)

 {

     if(l>r)return;

     int mid=(l+r)>>;

     tr[q[mid]].fa=q[last];

     tr[q[last]].ch[mid>last]=q[mid];

     build(l,mid-,mid);build(mid+,r,mid);

     pushup(q[mid]);

 }

 void print(int x)

 {

     printf("[%d] [fa]%d [v]%lld [sum]%lld [t]%d [num]%d\n",x,tr[x].fa,tr[x].v,tr[x].sum,tr[x].t,tr[x].num);

     int l=tr[x].ch[],r=tr[x].ch[];

     if(l)print(l);if(r)print(r);

 }

 void query()

 {

     int x=read();

     splay(x+,root);

     printf("%lld\n",tr[tr[x+].ch[]].sum+tr[x+].v);

 }

 void change()

 {

     int x=read(),y=read();

     split(x+,x+n+);

     int yi=tr[root].ch[],xi=tr[yi].ch[];

     tr[yi].ch[]=;pushup(yi);pushup(root);

     splay(y+,root);

     int u=fmin(tr[y+].ch[]);

     splay(u,tr[y+].ch[]);

     tr[xi].fa=u;

     tr[u].ch[]=xi;

     pushup(u);pushup(root);

 }

 void add()

 {

     int x=read();long long tag=read();

     split(x+,x+n+);

     int yi=tr[root].ch[],xi=tr[yi].ch[];

     tr[xi].tag+=tag;tr[xi].sum+=tag*tr[xi].num;tr[xi].v+=tag*tr[xi].t;

     pushup(yi);pushup(root);

 }

 int main()

 {

     char str[];

     n=read();

     for(int i=;i<=n;i++)f=read(),insert(f,i);

     for(int i=;i<=n;i++)f=read(),tr[i+].v=f,tr[i+].t=,tr[i+n+].v=-f,tr[i+n+].t=-;

     cnt=;dfs();root=q[n+];

     q[]=;q[*n+]=*n+;

     build(,*n+,);

     m=read();

     while(m--)

     {

         scanf("%s",str);

         if(str[]=='Q')query();

         if(str[]=='C')change();

         if(str[]=='F')add();

     }

     return ;

 }

splay的分裂合并【Time:19964 ms】

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 const int N=;

 struct node{int ch[],fa,t,num;long long v,sum,tag;}tr[N<<];

 struct edge{int next,to;}e[N];

 int n,m,f,root,cnt;

 int head[N],q[N<<],s[N<<];

 int read()

 {

     int x=,f=;char c=getchar();

     while(c<''||c>''){if(c=='-')f=-;c=getchar();}

     while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

     return x*f;

 }

 void insert(int a,int b){cnt++;e[cnt].to=b;e[cnt].next=head[a];head[a]=cnt;}

 void dfs(int x)

 {

     q[++cnt]=x+;

     for(int i=head[x];i;i=e[i].next)dfs(e[i].to);

     q[++cnt]=x+n+;

 }

 void add(int x,long long tag){tr[x].sum+=tag*tr[x].num;tr[x].v+=tag*tr[x].t;}

 void pushup(int x)

 {

     int l=tr[x].ch[],r=tr[x].ch[];

     tr[x].num=tr[l].num+tr[r].num+tr[x].t;

     tr[x].sum=tr[l].sum+tr[r].sum+tr[x].v;

 }

 void pushdown(int x)

 {

     int l=tr[x].ch[],r=tr[x].ch[];long long tag=tr[x].tag;

     if(l)tr[l].tag+=tag,add(l,tag);

     if(r)tr[r].tag+=tag,add(r,tag);

     tr[x].tag=;

 }

 void rotate(int x,int& k)

 {

     int y=tr[x].fa,z=tr[y].fa,l,r;

     if(tr[y].ch[]==x)l=;else l=;r=l^;

     if(y==k)k=x;

     else{if(tr[z].ch[]==y)tr[z].ch[]=x;else tr[z].ch[]=x;}

     tr[x].fa=z;tr[y].fa=x;tr[tr[x].ch[r]].fa=y;

     tr[y].ch[l]=tr[x].ch[r];tr[x].ch[r]=y;

     pushup(y);pushup(x);

 }

 void splay(int x,int& k)

 {

     int top=;s[++top]=x;

     for(int i=x;tr[i].fa;i=tr[i].fa)s[++top]=tr[i].fa;

     for(int i=top;i;i--)if(tr[s[i]].tag)pushdown(s[i]);

     while(x!=k)

     {

         int y=tr[x].fa,z=tr[y].fa;

         if(y!=k)

         {

             if((tr[y].ch[]==x)^(tr[z].ch[]==y))rotate(x,k);

             else rotate(y,k);

         }

         rotate(x,k);

     }

 }

 int find(int x){while(tr[x].ch[])x=tr[x].ch[];return x;}

 void build(int l,int r,int last)

 {

     if(l>r)return;

     int mid=(l+r)>>;

     tr[q[mid]].fa=q[last];

     tr[q[last]].ch[mid>last]=q[mid];

     build(l,mid-,mid);build(mid+,r,mid);

     pushup(q[mid]);

 }

 int merge(int r1,int r2)

 {

     int w=find(r1);

     splay(w,r1);

     tr[w].ch[]=r2;

     tr[r2].fa=w;

     pushup(w);

     return w;

 }

 void cutl(int x,int rt,int& r1,int& r2)

 {

     splay(x,rt);

     r1=tr[x].ch[];r2=x;

     tr[x].ch[]=;

     tr[r1].fa=;

     pushup(x);

 }

 void cutr(int x,int rt,int& r1,int& r2)

 {

     splay(x,rt);

     r1=x;r2=tr[x].ch[];

     tr[x].ch[]=;

     tr[r2].fa=;

     pushup(x);

 }

 void query()

 {

     int x=read()+;

     splay(x,root);

     printf("%lld\n",tr[tr[x].ch[]].sum+tr[x].v);

 }

 void change()

 {

     int x=read()+,y=x+n,k=read()+,p1,p2,p3;

     cutl(x,root,p1,p2);

     cutr(y,p2,p2,p3);

     cutr(k,merge(p1,p3),p1,p3);

     root=merge(merge(p1,p2),p3);

 }

 void add()

 {

     int x=read()+,y=x+n;long long tag=read();

     splay(x,root);splay(y,tr[x].ch[]);

     int z=tr[y].ch[];

     add(x,tag);add(y,tag);

     add(z,tag);tr[z].tag+=tag;

     pushup(y);pushup(x);

 }

 int main()

 {

     char str[];

     n=read();

     for(int i=;i<=n;i++)f=read(),insert(f,i);

     for(int i=;i<=n+;i++)f=read(),tr[i].v=f,tr[i].t=,tr[i+n].v=-f,tr[i+n].t=-;

     cnt=;q[++cnt]=;dfs();q[++cnt]=*n+;

     build(,*n+,);root=q[n+];

     m=read();

     while(m--)

     {

         scanf("%s",str);

         if(str[]=='Q')query();

         if(str[]=='C')change();

         if(str[]=='F')add();

     }

     return ;

 }

巴特西