首页 技术 正文
技术 2022年11月24日
0 收藏 825 点赞 2,378 浏览 4259 个字

【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

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.保证操作合法。

题解:参考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;
}

微信扫一扫

支付宝扫一扫

本文网址:https://www.zhankr.net/142030.html

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:875 阅读:5,090
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:806 阅读:3,508
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:565 阅读:4,320
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:730 阅读:4,314
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:4,920
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:3,105
发表评论
暂无评论

还没有评论呢,快来抢沙发~

助力内容变现

将您的收入提升到一个新的水平

点击联系客服

在线时间:8:00-16:00

客服电话

400-888-8888

客服邮箱

ceotheme@ceo.com

扫描二维码

关注微信公众号

扫描二维码

手机访问本站