首页 > 代码库 > 【BZOJ3786】星系探索 DFS序+Splay
【BZOJ3786】星系探索 DFS序+Splay
【BZOJ3786】星系探索
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
1
1
4 5 7
5
Q 2
F 1 3
Q 2
C 2 3
Q 2
Sample Output
15
25
HINT
n<=100000,m<=300000,1<di,xi<=n,wi,qi<=100000.保证操作合法。
题解:参考http://blog.csdn.net/PoPoQQQ/article/details/41649197
如果没有C操作,我们完全可以树剖搞定,但树剖不能实现修改子树
于是我们想到在DFS序中,先求出入栈出栈序,那么子树就变成了一段连续的区间,这样我们就可以用Splay来进行区间移动,并维护区间和
那么在入栈出栈序中怎么求出到根节点的路径上的点权和呢?
我们可以给入栈出栈序上的每个点乘以一个系数,入栈为1,出栈为-1,这样我们只要求一个前缀和就可以啦。但我们还要维护Splay中区间的系数和,因为这在区间修改时会用到
好久没写Splay了,以前写的的Splay都是直来直去的区间,今天调试时各种WA,各种TLE,各种RE,渣电脑快被我搞炸了~
还有注意这题要开long long
#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> using namespace std; const int maxn=100010; typedef long long ll; struct node { ll fa,ch[2],size; ll tag,sw,sv,w,v; }p[maxn<<1]; ll n,m,tot,cnt,root; ll f[maxn],to[maxn],next[maxn],head[maxn],q[maxn<<1]; char str[5]; ll readin() { ll ret=0; char gc; while(gc<‘0‘||gc>‘9‘) gc=getchar(); while(gc>=‘0‘&&gc<=‘9‘) ret=ret*10+gc-‘0‘,gc=getchar(); return ret; } void dfs(ll x) { q[++tot]=x; for(ll i=head[x];i!=-1;i=next[i]) dfs(to[i]); q[++tot]=x+n; } void add(ll a,ll b) { to[cnt]=b; next[cnt]=head[a]; head[a]=cnt++; } void pushup(ll x) { p[x].sw=p[p[x].ch[0]].sw+p[p[x].ch[1]].sw+p[x].w; p[x].sv=p[p[x].ch[0]].sv+p[p[x].ch[1]].sv+p[x].v; p[x].size=p[p[x].ch[0]].size+p[p[x].ch[1]].size+1; } void pushdown(ll x) { if(p[x].ch[0]) p[p[x].ch[0]].sw+=p[p[x].ch[0]].sv*p[x].tag,p[p[x].ch[0]].w+=p[p[x].ch[0]].v*p[x].tag,p[p[x].ch[0]].tag+=p[x].tag; if(p[x].ch[1]) p[p[x].ch[1]].sw+=p[p[x].ch[1]].sv*p[x].tag,p[p[x].ch[1]].w+=p[p[x].ch[1]].v*p[x].tag,p[p[x].ch[1]].tag+=p[x].tag; p[x].tag=0; } void build(ll l,ll r,ll last) { if(l>r) return ; ll mid=l+r>>1; p[q[mid]].fa=q[last]; if(last) p[q[last]].ch[mid>last]=q[mid]; build(l,mid-1,mid),build(mid+1,r,mid); pushup(q[mid]); } void rotate(ll x,ll &k) { ll y=p[x].fa,z=p[y].fa,d=(x==p[y].ch[1]); if(y==k) k=x; else p[z].ch[y==p[z].ch[1]]=x; p[x].fa=z,p[y].fa=x,p[y].ch[d]=p[x].ch[d^1]; if(p[x].ch[d^1]) p[p[x].ch[d^1]].fa=y; p[x].ch[d^1]=y; pushup(y),pushup(x); } ll qrank(ll x) { ll ret; if(x==root) ret=p[p[x].ch[0]].size+1; else if(x==p[p[x].fa].ch[0]) ret=qrank(p[x].fa)-p[p[x].ch[1]].size-1; else ret=qrank(p[x].fa)+p[p[x].ch[0]].size+1; pushdown(x); return ret; } void splay(ll x,ll &k) { while(x!=k) { ll y=p[x].fa,z=p[y].fa; if(y!=k) { if((p[y].ch[0]==x)^(p[z].ch[0]==y)) rotate(x,k); else rotate(y,k); } rotate(x,k); } } ll find(ll x,ll y) { pushdown(x); if(p[p[x].ch[0]].size+1==y) return x; if(y<=p[p[x].ch[0]].size) return find(p[x].ch[0],y); else return find(p[x].ch[1],y-p[p[x].ch[0]].size-1); } void _Q() { ll x; x=readin(); qrank(x); splay(x,root); printf("%lld\n",p[p[x].ch[0]].sw+p[x].w); } void _C() { ll x,y,u,t; x=readin(),y=readin(); splay(find(root,qrank(x)-1),root); splay(find(root,qrank(x+n)+1),p[root].ch[1]); u=p[p[root].ch[1]].ch[0]; p[p[root].ch[1]].ch[0]=0; pushup(p[root].ch[1]),pushup(root); qrank(y),qrank(y+n); splay(y,root); splay(y+n,p[root].ch[1]); t=p[root].ch[1]; while(p[t].ch[0]) t=p[t].ch[0]; qrank(t); p[t].ch[0]=u,p[u].fa=t; while(t) pushup(t),t=p[t].fa; } void _F() { ll x,y; x=readin(),y=readin(); splay(find(root,qrank(x)-1),root); splay(find(root,qrank(x+n)+1),p[root].ch[1]); p[p[p[root].ch[1]].ch[0]].sw+=p[p[p[root].ch[1]].ch[0]].sv*y; p[p[p[root].ch[1]].ch[0]].w+=p[p[p[root].ch[1]].ch[0]].v*y; p[p[p[root].ch[1]].ch[0]].tag+=y; } int main() { n=readin(); ll i; memset(head,-1,sizeof(head)); for(i=2;i<=n;i++) f[i]=readin(),add(f[i],i); for(i=1;i<=n;i++) p[i].w=readin(),p[i+n].w=-p[i].w,p[i].v=1,p[i+n].v=-1; tot=1; dfs(1); root=q[n+1],q[1]=2*n+1,q[2*n+2]=2*n+2; build(1,2*n+2,0); m=readin(); for(i=1;i<=m;i++) { scanf("%s",str); switch(str[0]) { case ‘Q‘:_Q(); break; case ‘C‘:_C(); break; case ‘F‘:_F(); break; } } return 0; }
【BZOJ3786】星系探索 DFS序+Splay