BZOJ3786星系探索——非旋转treap(平衡树动态维护dfs序)

Stella981
• 阅读 499

题目描述

物理学家小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可能会进行若干次实验,对于他的每一次实验,请你告诉他这一次实验能量收集器的最终能量是多少。

输入

第一行一个整数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.

输出

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

样例输入

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

样例输出

9
15
25

提示

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

如果没有迁移子树操作考虑怎么做?

求出原树出栈入栈序(下文用dfs序代替),对于入栈点权值为正(即val[x]),对于出站点权值为负(即-val[x]),那么询问就是求询问点在dfs序上入栈点的前缀和(不在这个点到根路径上的点出栈点和入栈点一定同时在询问点的前边,正负权值抵消)。

对于修改一定是dfs序上的一段区间,用线段树区间修改即可,因为每个点可能是正权可能是负权,因此还要维护区间正权点数与负权点数之差。

那么现在有了子树迁移操作,dfs序是动态的了,显然线段树无法实现,那么用平衡树就好了。

将操作点子树从treap中分裂出来然后插入到它新的父节点入栈点后面即可。

但因为这道题我们只知道dfs序上每个点对应平衡树上节点的编号(建树时开两个数组分别存一下),所以要再维护出平衡树上每个点的父节点然后每次分裂前先从操作点往上找到根节点来得到这个点在平衡树上的具体位置(即它现在是dfs序的第几个点)再从根正常分裂。

这道题严重卡常,建议用上所有优化,蒟蒻的我差点没卡过去QAQ。

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long 
using namespace std;
char buf[100000],*p1,*p2;
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
__attribute__((optimize("-O3")))int rd() {
    register int x=0;register char ch=nc();
    while(ch<'0'||ch>'9') ch=nc();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=nc();
    return x;
}
int n,m;
int x,y;
int tot;
int cnt;
int res;
int root;
int a,b,c;
int head[200010];
int to[200010];
int next[200010];
int num[200010];
int sig[200010];
ll sum[200010];
int v[200010];
int val[200010];
int pos[200010];
int size[200010];
int ls[200010];
int rs[200010];
int f[200010];
int r[200010];
int s[200010];
int t[200010];
int p[200010];
int q[200010];
inline void add(int x,int y)
{
    tot++;
    next[tot]=head[x];
    head[x]=tot;
    to[tot]=y;
}
inline int build(int val,int k)
{
    int rt=++cnt;
    r[rt]=rand();
    size[rt]=1;
    v[rt]=val*k;
    sum[rt]=1ll*v[rt];
    sig[rt]=k;
    num[rt]=sig[rt];
    return rt;
}
inline void pushup(int rt)
{
    size[rt]=size[ls[rt]]+size[rs[rt]]+1;
    num[rt]=sig[rt];
    sum[rt]=1ll*v[rt];
    if(ls[rt])
    {
        num[rt]+=num[ls[rt]];
        sum[rt]+=sum[ls[rt]];
    }
    if(rs[rt])
    {
        num[rt]+=num[rs[rt]];
        sum[rt]+=sum[rs[rt]];
    }
}
inline void pushdown(int rt)
{
    if(pos[rt])
    {
        pos[ls[rt]]+=pos[rt];
        pos[rs[rt]]+=pos[rt];
        sum[ls[rt]]+=1ll*num[ls[rt]]*pos[rt];
        sum[rs[rt]]+=1ll*num[rs[rt]]*pos[rt];
        v[ls[rt]]+=sig[ls[rt]]*pos[rt];
        v[rs[rt]]+=sig[rs[rt]]*pos[rt];
        pos[rt]=0;
    }
}
inline int merge(int x,int y)
{
    pushdown(x);
    pushdown(y);
    if(!x||!y)
    {
        return x+y;
    }
    if(r[x]<r[y])
    {
        rs[x]=merge(rs[x],y);
        if(rs[x])
        {
            f[rs[x]]=x;
        }
        pushup(x);
        return x;
    }
    else
    {
        ls[y]=merge(x,ls[y]);
        if(ls[y])
        {
            f[ls[y]]=y;
        }
        pushup(y);
        return y;
    }
}
inline void split(int rt,int &x,int &y,int k)
{
    pushdown(rt);
    if(!rt)
    {
        x=y=0;
        return ;
    }
    if(size[ls[rt]]>=k)
    {
        y=rt;
        split(ls[rt],x,ls[y],k);
        if(ls[y])
        {
            f[ls[y]]=y;
        }
        pushup(rt);
    }
    else
    {
        x=rt;
        split(rs[rt],rs[x],y,k-size[ls[rt]]-1);
        if(rs[x])
        {
            f[rs[x]]=x;
        }
        pushup(rt);
    }
}
inline int get_size(int rt)
{
    int ans=0;
    int flag=1;
    while(rt)
    {
        if(flag)
        {
            ans+=size[ls[rt]]+1;
        }
        flag=(rt==rs[f[rt]]);
        rt=f[rt];
    }
    return ans;
}
inline void dfs(int x)
{
    s[x]=build(val[x],1);
    root=merge(root,s[x]);
    for(int i=head[x];i;i=next[i])
    {
        dfs(to[i]);
    }
    t[x]=build(val[x],-1);
    root=merge(root,t[x]);
}
int main()
{
    srand(12378);
    n=rd();
    for(int i=2;i<=n;i++)
    {
        x=rd();
        add(x,i);
    }
    for(int i=1;i<=n;i++)
    {
        val[i]=rd();
    }
    dfs(1);
    m=rd();
    while(m--)
    {
        char op=nc();
        while(op!='C'&&op!='Q'&&op!='F')op=nc();
        int x=rd();
        if(op=='Q')
        {
            res=get_size(s[x]);
            split(root,a,b,res);
            f[a]=f[b]=0;
            printf("%lld\n",sum[a]);
            root=merge(a,b);
        }
        else if(op=='F')
        {
            y=rd();
            res=get_size(t[x]);
            split(root,b,c,res);
            f[b]=f[c]=0;
            res=get_size(s[x]);
            split(b,a,b,res-1);
            f[a]=f[b]=0;
            pos[b]+=y;
            sum[b]+=1ll*num[b]*y;
            v[b]+=sig[b]*y;
            root=merge(merge(a,b),c);
        }
        else
        {
            y=rd();
            res=get_size(t[x]);
            split(root,b,c,res);
            f[b]=f[c]=0;
            res=get_size(s[x]);
            split(b,a,b,res-1);
            f[a]=f[b]=0;
            root=merge(a,c);
            res=get_size(s[y]);
            split(root,a,c,res);
            f[a]=f[c]=0;
            root=merge(merge(a,b),c);
        }
    }
}
点赞
收藏
评论区
推荐文章
OkHttp 通用抓包方式分析,以某小视频App为例
一、目标太难了,这年头抓包越来越难了,某小视频更新频发,我们之前屏蔽QUIC的方案貌似也失效了。幸好我们还有OkHttpLoggerFridaTIP:v9.10.10.22596着急的同学可以直接拉到后面,加入知识星球取js吧。有理想的同学建议好好研究下原理,下次就可以自己适配了。二、步骤原理分析在这篇文章里面我们分析了v8.0使用
东方客主 东方客主
3年前
一篇文章弄明白Javascript
在一片混沌中,一个叫Function的函数开天辟地,自己创建了自己。于是,一个叫JavaScript的星球诞生了。图一:创建了自己的Function新诞生
Wesley13 Wesley13
2年前
TARS星球社区,2021元旦快乐!
!(https://oscimg.oschina.net/oscnet/d668da440ab94142b68217ba937f8292.jpg)点“在看”让TARS小姐姐变好看!(https://oscimg.oschina.net/oscnet/49f9e5b64a8146a58aa4a89e86f9b747.gif)!
Wesley13 Wesley13
2年前
Java 8 停止维护,Java 9 难产,IDEA 2018 发布,还有……
祝大家五一劳动节快乐,工作顺利!又到了总结上个月干货的时候了,这个月我们带来了各种Java技术干货,各种送书抽奖福利,各种面试题分享,各种最新动态资讯等。5.1重磅活动|区块链免费送书&星球特价(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fmp.weixin.
Stella981 Stella981
2年前
Gitee星球向你发出庆典邀请函,你来吗?
!(https://oscimg.oschina.net/oscnet/4915a1e1054cebd005115fc091af96fc229.png)不知不觉间,Gitee来到了上线的第七个年头七年,说长不长,说短不短感谢每一个你们在七年里的陪伴!(https://oscimg.oschina.net/oscnet/f85
Wesley13 Wesley13
2年前
Java之if语句
!(https://oscimg.oschina.net/oscnet/bf8aa48ba2214bd88b45c159ae697234.gif)推荐阅读:《知识星球介绍(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fmp.weixin.
燕青 燕青
8个月前
群星Stellaris for mac(策略游戏)+dlc
是一款科幻策略类游戏,于2016年首次发布。该游戏采用了大量的实时战略元素和4X类型的游戏机制,并通过对宇宙、时间和其他种族的探索来提供一个无限的游戏世界。其主要特点包括:1.宇宙探索:玩家可以探索虚构宇宙中的星球、行星和恒星系统,并与其他外星智慧生命体进
Python进阶者 Python进阶者
11个月前
盘点一个可以一键免费下载图片的谷歌插件
大家好,我是皮皮。一、前言前几天在Python知识星球里边看到【七年】大佬推荐的一个谷歌浏览器插件,可以一键下载浏览器中的图片或者PPT,这里也推荐给大家,一起来看看吧!二、实现过程这个插件是免费的,非常奈斯,但是在谷歌浏览器中下载的时候,需要借助ti子,
Python进阶者 Python进阶者
10个月前
ChatGPT 实用小案例分享——使用Python重命名附件和统计发票合计金额
大家好,我是皮皮。一、前言前几天在【志军】的星球看到了一个有意思的ChatGPT分享,正好喝Python相关的,一起来看看吧。ChatGPT实用小案例分享。如果你在高德或者滴滴上申请过开票,应该知道它们会给我们发一封邮件,发票和行程单都会放在附件中。由于高
公孙晃 公孙晃
8个月前
Mac电脑模拟建造游戏:伊始之地Terra Nil for Mac
是一款Mac上的模拟建造游戏,玩家将在荒芜的星球上开展探险,通过采集资源、研究技术、建立基地等方式来打造一个全新的生态系统。游戏画面精美,音效逼真,同时支持中文语言。在游戏中,玩家需要灵活运用各种资源和技术,解决生存和发展的问题,逐步建立起一个繁荣的生态系