[BZOJ3786]星系探索

本文主要是介绍[BZOJ3786]星系探索，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

星系探索

题解

一道ETT板子题
笔者最开始用FHQ_Treap打的ETT，忘记可以沿$fa$算出它的欧拉序，一直没调出来，于是就改用splay了。

ETT的模板。其实我觉得叫它平衡树板子就可以了
我们可以先通过欧拉序建出一颗平衡树来，令$i{n}_x$为点$x$的入欧拉序，$ou{t}_x$为点$x$的出欧拉序。
容易发现，$i{n}_{root}$到$i{n}_v$的区间中删去既有出又有入的点，得到的就是从根到点$v$的入点的路径。
于是，第一个操作求这条路径的和我们可以转化为求这个区间之和。将点$ou{t}_x$的权值赋值为点$i{n}_x$的相反数，这样统计得到的区间的和可以将没有经过的点消去，得到答案。
我们又知道，从$i{n}_x$到$ou{t}_x$的区间是点$x$的子树，所以只需要将这个区间拆下来，接到其后面就可以完成操作二了。
操作三也就是平衡树的常规操作，打个懒标记就能解决。

源码

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define MAXN 200005 
typedef long long LL;
const LL INF=0x7f7f7f7f;
typedef unsigned long long uLL;
typedef pair<int,int> pii;
template<typename _T>
void read(_T &x){_T f=1;x=0;char s=getchar();while('0'>s||'9'<s){if(s=='-')f=-1;s=getchar();}while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}x*=f;
} 
struct edge{int to,nxt;}e[MAXN];
int head[MAXN],tot,a[MAXN],n,m;
void addEdge(int u,int v){e[++tot]=(edge){v,head[u]};head[u]=tot;}
class Splay{private:int siz[MAXN],ch[MAXN][2],val[MAXN];int lzy[MAXN],fa[MAXN],cnt[MAXN];int sta[MAXN],stak,root;LL sum[MAXN]; void pushup(int rt){siz[rt]=siz[ch[rt][0]]+siz[ch[rt][1]]+cnt[rt];sum[rt]=sum[ch[rt][0]]+sum[ch[rt][1]]+1ll*cnt[rt]*val[rt];}void work(int rt,int w){if(!rt)return ;val[rt]+=w;lzy[rt]+=w;sum[rt]+=1ll*siz[rt]*w;}void pushdown(int rt){if(!lzy[rt])return ;work(ch[rt][0],lzy[rt]);work(ch[rt][1],lzy[rt]);lzy[rt]=0;}void rotate(int x,int &k){//printf("%d %d\n",x,k);int y=fa[x],z=fa[y],l,r;if(ch[y][0]==x)l=0;else l=1;r=l^1;if(y==k)k=x;else{if(ch[z][0]==y)ch[z][0]=x;else ch[z][1]=x;}fa[x]=z;fa[y]=x;fa[ch[x][r]]=y;ch[y][l]=ch[x][r];ch[x][r]=y;pushup(y);pushup(x);}void splay(int x,int &k){//printf("%d %d\n",x,k);sta[++stak]=x;for(int i=x;i^root;i=fa[i])sta[++stak]=fa[i];for(int i=stak;i;i--)pushdown(sta[i]);stak=0;while(x!=k){int y=fa[x],z=fa[y];if(y!=k){int d1=(ch[z][0]==y),d2=(ch[y][0]==x);if(d1^d2)rotate(x,k);else rotate(y,k);}rotate(x,k);}}int findL(int x){while(ch[x][0])x=ch[x][0];return x;}int findR(int x){while(ch[x][1])x=ch[x][1];return x;}public:void insert(int x,int v,int w){if(!root)root=x;else fa[x]=root,ch[root][1]=x;val[x]=v;cnt[x]=w;pushup(x);splay(x,root);}LL query(int x){splay(x,root);return sum[ch[x][0]]+1ll*cnt[x]*val[x];}void link(int x,int y){splay(x,root);int t1=findR(ch[root][0]);splay(x+n+1,root);int t2=findL(ch[root][1]);splay(t1,root);splay(t2,ch[t1][1]);int z=ch[t2][0];fa[z]=ch[t2][0]=0;splay(y,root);int t3=findL(ch[y][1]);splay(t3,ch[y][1]);fa[z]=t3;ch[t3][0]=z;}void modify(int x,int w){splay(x,root);int t1=findR(ch[root][0]);splay(x+n+1,root);int t2=findL(ch[root][1]);splay(t1,root);splay(t2,ch[t1][1]);work(ch[t2][0],w);}void build(int u){insert(u+1,a[u],1);for(int i=head[u];i;i=e[i].nxt)build(e[i].to);insert(u+n+2,a[u],-1);}
}T;
signed main(){read(n);for(int i=2,f;i<=n;i++)read(f),addEdge(f,i);for(int i=1;i<=n;i++)read(a[i]);T.insert(1,0,0);T.build(1);T.insert(2*n+3,0,0);read(m);char opt[20]={};while(m--){scanf("%s",opt);int x,y;if(opt[0]=='Q')read(x),printf("%lld\n",T.query(x+1));if(opt[0]=='C')read(x),read(y),T.link(x+1,y+1);if(opt[0]=='F')read(x),read(y),T.modify(x+1,y);}return 0;
}

谢谢！！！

这篇关于[BZOJ3786]星系探索的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---