首页 > 代码库 > 【bzoj 3786】星系探索
【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
1
1
4 5 7
5
Q 2
F 1 3
Q 2
C 2 3
Q 2
Sample Output
9
15
25
15
25
HINT
n<=100000,m<=300000,1<di,xi<=n,wi,qi<=100000.保证操作合法。注意w_i>=0。
纪念一下一道调了两天发现自己忘开long long的题>_<
直接查找前驱后继【Time:25484 ms】
1 #include<cstdio>
2 #include<algorithm>
3 #include<cstring>
4 using namespace std;
5 const int inf=0x3f3f3f3f;
6 const int N=100010;
7 struct node{int ch[2],size,fa,t,num;long long v,sum,tag;}tr[N<<1];
8 struct edge{int next,to;}e[N];
9 int n,m,f,root,cnt;
10 int head[N],q[N<<1],s[N];
11 int read()
12 {
13 int x=0,f=1;char c=getchar();
14 while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();}
15 while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();}
16 return x*f;
17 }
18 void insert(int a,int b){cnt++;e[cnt].to=b;e[cnt].next=head[a];head[a]=cnt;}
19 void dfs(int x)
20 {
21 q[++cnt]=x+1;
22 for(int i=head[x];i;i=e[i].next)dfs(e[i].to);
23 q[++cnt]=x+n+1;
24 }
25 void pushup(int x)
26 {
27 int l=tr[x].ch[0],r=tr[x].ch[1];
28 tr[x].size=tr[l].size+tr[r].size+1;
29 tr[x].num=tr[l].num+tr[r].num+tr[x].t;
30 tr[x].sum=tr[l].sum+tr[r].sum+tr[x].v;
31 }
32 void pushdown(int x)
33 {
34 int l=tr[x].ch[0],r=tr[x].ch[1];long long tag=tr[x].tag;
35 if(l)tr[l].tag+=tag,tr[l].sum+=tag*tr[l].num,tr[l].v+=tag*tr[l].t;
36 if(r)tr[r].tag+=tag,tr[r].sum+=tag*tr[r].num,tr[r].v+=tag*tr[r].t;
37 tr[x].tag=0;
38 }
39 void rotate(int x,int& k)
40 {
41 int y=tr[x].fa,z=tr[y].fa,l,r;
42 if(tr[y].ch[0]==x)l=0;else l=1;r=l^1;
43 if(y==k)k=x;
44 else{if(tr[z].ch[0]==y)tr[z].ch[0]=x;else tr[z].ch[1]=x;}
45 tr[x].fa=z;tr[y].fa=x;tr[tr[x].ch[r]].fa=y;
46 tr[y].ch[l]=tr[x].ch[r];tr[x].ch[r]=y;
47 pushup(y);pushup(x);
48 }
49 void splay(int x,int& k)
50 {
51 int top=0;s[++top]=x;
52 for(int i=x;tr[i].fa;i=tr[i].fa)s[++top]=tr[i].fa;
53 for(int i=top;i;i--)if(tr[s[i]].tag)pushdown(s[i]);
54 while(x!=k)
55 {
56 int y=tr[x].fa,z=tr[y].fa;
57 if(y!=k)
58 {
59 if((tr[y].ch[0]==x)^(tr[z].ch[0]==y))rotate(x,k);
60 else rotate(y,k);
61 }
62 rotate(x,k);
63 }
64 }
65 int fmin(int x){while(tr[x].ch[0])x=tr[x].ch[0];return x;}
66 int fmax(int x){while(tr[x].ch[1])x=tr[x].ch[1];return x;}
67 void split(int l,int r)
68 {
69 splay(l,root);int x=fmax(tr[l].ch[0]);
70 splay(r,root);int y=fmin(tr[r].ch[1]);
71 splay(x,root);splay(y,tr[x].ch[1]);
72 }
73 void build(int l,int r,int last)
74 {
75 if(l>r)return;
76 int mid=(l+r)>>1;
77 tr[q[mid]].fa=q[last];
78 tr[q[last]].ch[mid>last]=q[mid];
79 build(l,mid-1,mid);build(mid+1,r,mid);
80 pushup(q[mid]);
81 }
82 void print(int x)
83 {
84 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);
85 int l=tr[x].ch[0],r=tr[x].ch[1];
86 if(l)print(l);if(r)print(r);
87 }
88 void query()
89 {
90 int x=read();
91 splay(x+1,root);
92 printf("%lld\n",tr[tr[x+1].ch[0]].sum+tr[x+1].v);
93 }
94 void change()
95 {
96 int x=read(),y=read();
97 split(x+1,x+n+1);
98 int yi=tr[root].ch[1],xi=tr[yi].ch[0];
99 tr[yi].ch[0]=0;pushup(yi);pushup(root);
100 splay(y+1,root);
101 int u=fmin(tr[y+1].ch[1]);
102 splay(u,tr[y+1].ch[1]);
103 tr[xi].fa=u;
104 tr[u].ch[0]=xi;
105 pushup(u);pushup(root);
106 }
107 void add()
108 {
109 int x=read();long long tag=read();
110 split(x+1,x+n+1);
111 int yi=tr[root].ch[1],xi=tr[yi].ch[0];
112 tr[xi].tag+=tag;tr[xi].sum+=tag*tr[xi].num;tr[xi].v+=tag*tr[xi].t;
113 pushup(yi);pushup(root);
114 }
115 int main()
116 {
117 char str[1];
118 n=read();
119 for(int i=2;i<=n;i++)f=read(),insert(f,i);
120 for(int i=1;i<=n;i++)f=read(),tr[i+1].v=f,tr[i+1].t=1,tr[i+n+1].v=-f,tr[i+n+1].t=-1;
121 cnt=1;dfs(1);root=q[n+1];
122 q[1]=1;q[2*n+2]=2*n+2;
123 build(1,2*n+2,0);
124 m=read();
125 while(m--)
126 {
127 scanf("%s",str);
128 if(str[0]==‘Q‘)query();
129 if(str[0]==‘C‘)change();
130 if(str[0]==‘F‘)add();
131 }
132 return 0;
133 }
分裂合并【Time:19964 ms】
1 #include<cstdio>
2 #include<algorithm>
3 #include<cstring>
4 using namespace std;
5 const int N=100010;
6 struct node{int ch[2],fa,t,num;long long v,sum,tag;}tr[N<<1];
7 struct edge{int next,to;}e[N];
8 int n,m,f,root,cnt;
9 int head[N],q[N<<1],s[N<<1];
10 int read()
11 {
12 int x=0,f=1;char c=getchar();
13 while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();}
14 while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();}
15 return x*f;
16 }
17 void insert(int a,int b){cnt++;e[cnt].to=b;e[cnt].next=head[a];head[a]=cnt;}
18 void dfs(int x)
19 {
20 q[++cnt]=x+1;
21 for(int i=head[x];i;i=e[i].next)dfs(e[i].to);
22 q[++cnt]=x+n+1;
23 }
24 void add(int x,long long tag){tr[x].sum+=tag*tr[x].num;tr[x].v+=tag*tr[x].t;}
25 void pushup(int x)
26 {
27 int l=tr[x].ch[0],r=tr[x].ch[1];
28 tr[x].num=tr[l].num+tr[r].num+tr[x].t;
29 tr[x].sum=tr[l].sum+tr[r].sum+tr[x].v;
30 }
31 void pushdown(int x)
32 {
33 int l=tr[x].ch[0],r=tr[x].ch[1];long long tag=tr[x].tag;
34 if(l)tr[l].tag+=tag,add(l,tag);
35 if(r)tr[r].tag+=tag,add(r,tag);
36 tr[x].tag=0;
37 }
38 void rotate(int x,int& k)
39 {
40 int y=tr[x].fa,z=tr[y].fa,l,r;
41 if(tr[y].ch[0]==x)l=0;else l=1;r=l^1;
42 if(y==k)k=x;
43 else{if(tr[z].ch[0]==y)tr[z].ch[0]=x;else tr[z].ch[1]=x;}
44 tr[x].fa=z;tr[y].fa=x;tr[tr[x].ch[r]].fa=y;
45 tr[y].ch[l]=tr[x].ch[r];tr[x].ch[r]=y;
46 pushup(y);pushup(x);
47 }
48 void splay(int x,int& k)
49 {
50 int top=0;s[++top]=x;
51 for(int i=x;tr[i].fa;i=tr[i].fa)s[++top]=tr[i].fa;
52 for(int i=top;i;i--)if(tr[s[i]].tag)pushdown(s[i]);
53 while(x!=k)
54 {
55 int y=tr[x].fa,z=tr[y].fa;
56 if(y!=k)
57 {
58 if((tr[y].ch[0]==x)^(tr[z].ch[0]==y))rotate(x,k);
59 else rotate(y,k);
60 }
61 rotate(x,k);
62 }
63 }
64 int find(int x){while(tr[x].ch[1])x=tr[x].ch[1];return x;}
65 void build(int l,int r,int last)
66 {
67 if(l>r)return;
68 int mid=(l+r)>>1;
69 tr[q[mid]].fa=q[last];
70 tr[q[last]].ch[mid>last]=q[mid];
71 build(l,mid-1,mid);build(mid+1,r,mid);
72 pushup(q[mid]);
73 }
74 int merge(int r1,int r2)
75 {
76 int w=find(r1);
77 splay(w,r1);
78 tr[w].ch[1]=r2;
79 tr[r2].fa=w;
80 pushup(w);
81 return w;
82 }
83 void cutl(int x,int rt,int& r1,int& r2)
84 {
85 splay(x,rt);
86 r1=tr[x].ch[0];r2=x;
87 tr[x].ch[0]=0;
88 tr[r1].fa=0;
89 pushup(x);
90 }
91 void cutr(int x,int rt,int& r1,int& r2)
92 {
93 splay(x,rt);
94 r1=x;r2=tr[x].ch[1];
95 tr[x].ch[1]=0;
96 tr[r2].fa=0;
97 pushup(x);
98 }
99 void query()
100 {
101 int x=read()+1;
102 splay(x,root);
103 printf("%lld\n",tr[tr[x].ch[0]].sum+tr[x].v);
104 }
105 void change()
106 {
107 int x=read()+1,y=x+n,k=read()+1,p1,p2,p3;
108 cutl(x,root,p1,p2);
109 cutr(y,p2,p2,p3);
110 cutr(k,merge(p1,p3),p1,p3);
111 root=merge(merge(p1,p2),p3);
112 }
113 void add()
114 {
115 int x=read()+1,y=x+n;long long tag=read();
116 splay(x,root);splay(y,tr[x].ch[1]);
117 int z=tr[y].ch[0];
118 add(x,tag);add(y,tag);
119 add(z,tag);tr[z].tag+=tag;
120 pushup(y);pushup(x);
121 }
122 int main()
123 {
124 char str[5];
125 n=read();
126 for(int i=2;i<=n;i++)f=read(),insert(f,i);
127 for(int i=2;i<=n+1;i++)f=read(),tr[i].v=f,tr[i].t=1,tr[i+n].v=-f,tr[i+n].t=-1;
128 cnt=0;q[++cnt]=1;dfs(1);q[++cnt]=2*n+2;
129 build(1,2*n+2,0);root=q[n+1];
130 m=read();
131 while(m--)
132 {
133 scanf("%s",str);
134 if(str[0]==‘Q‘)query();
135 if(str[0]==‘C‘)change();
136 if(str[0]==‘F‘)add();
137 }
138 return 0;
139 }
【bzoj 3786】星系探索
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。