BZOJ3786: 星系探索（伪ETT）

题面

题解

坑啊……我好像把\(Splay\)的东西全忘光了……

\(ETT\)（\(Euler\ Tour\ Tree\)）是一种可以资瓷比\(LCT\)更多功能的数据结构，然而不管是功能还是复杂度都远远比不上\(TopTree\)和\(LCT\)（然而我似乎连\(TopTree\)都不会……）

然而一般情况下我们需要用到的只有伪\(ETT\)，用人话说就是用\(Splay\)维护欧拉序，进栈的时候值为\(+v\)，出栈的时候值为\(-v\)，那么\(1\)到\(u\)的路径上的所有数之和就是\(dfs\)序上\(ls[1]\)到\(ls[u]\)的所有数之和了（虽然看别的大佬的博客说这东西资瓷查询任意两点间路径和……然而咱并不明白该怎么搞……如果有知道的可以在下面告诉咱一声么qwq）

换根操作的话，就相当于提出一个区间放到另一个地方，\(Splay\)一下就好了

//minamoto

#include<bits/stdc++.h>

#define R register

#define ll long long

#define inline __inline__ __attribute__((always_inline))

#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)

#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)

#define go(u) for(int i=head[u],v=E[i].v;i;i=E[i].nx,v=E[i].v)

using namespace std;

char buf[1<<21],*p1=buf,*p2=buf;

inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}

int read(){

    R int res,f=1;R char ch;

    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);

    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');

    return res*f;

}

inline char getop(){R char ch;while((ch=getc())>'Z'||ch<'A');return ch;}

char sr[1<<21],z[20];int C=-1,Z=0;

inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}

void print(R ll x){

    if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x;

    while(z[++Z]=x%10+48,x/=10);

    while(sr[++C]=z[Z],--Z);sr[++C]='\n';

}

const int N=2e5+5;

struct eg{int v,nx;}E[N];int head[N],tot;

inline void add(R int u,R int v){E[++tot]={v,head[u]},head[u]=tot;}

struct node;typedef node* ptr;

struct node{

	ptr fa,lc,rc;int sz,ty;ll sum,t,v;

	inline node();

	inline void init(R int x,R int s){sz=ty=s,v=sum=x;}

	inline void ppd(R ll x){sum+=x*sz,v+=x*ty,t+=x;}

	inline void pd(){if(t)lc->ppd(t),rc->ppd(t),t=0;}

	inline ptr upd(){sum=lc->sum+rc->sum+v,sz=lc->sz+rc->sz+ty;return this;}

}e[N],*rt;

inline node::node(){lc=rc=fa=e;}

void push(ptr rt,ptr p){if(p!=rt)push(rt,p->fa);p->pd();}

void rotate(ptr &rt,ptr p){

	ptr s=p->fa,t=s->fa;

	if(s!=rt)(t->lc==s?t->lc:t->rc)=p;else rt=p;

	p->fa=t,s->fa=p;

	if(s->lc==p)s->lc=p->rc,p->rc->fa=s,p->rc=s->upd();

		else s->rc=p->lc,p->lc->fa=s,p->lc=s->upd();

}

ptr splay(ptr &rt,ptr p){

	push(rt,p);

	while(p!=rt){

		if(p->fa!=rt)rotate(rt,p->fa->lc==p^p->fa->fa->lc==p->fa?p:p->fa);

		rotate(rt,p);

	}

	return p->upd();

}

inline ptr lst(ptr p){p=splay(rt,p)->lc;while(p->rc!=e)p=p->rc;return p;}

inline ptr nxt(ptr p){p=splay(rt,p)->rc;while(p->lc!=e)p=p->lc;return p;}

inline ptr split(ptr s,ptr t){s=lst(s),t=nxt(t),splay(rt,s);return splay(s->rc,t);}

int a[N],val[N],ls[N],rs[N],tim;

void dfs(int u){

	ls[u]=++tim,val[tim]=u;

	go(u)dfs(v);

	rs[u]=++tim,val[tim]=-u;

}

void build(ptr &p,int l,int r,ptr fa){

	int mid=(l+r)>>1;p=e+mid,p->fa=fa;

	val[mid]>0?p->init(a[val[mid]],1):p->init(-a[-val[mid]],-1);

	if(l<mid)build(p->lc,l,mid-1,p);

	if(mid<r)build(p->rc,mid+1,r,p);

	p->upd();

}

inline ll get(R int x){return split(e+ls[1],e+ls[x])->lc->sum;}

void move(int x,int y){

	ptr s=split(e+ls[x],e+rs[x]),t=s->lc;

	s->lc=t->fa=e,s->upd(),s->fa->upd();

	splay(rt,e+ls[y]),s=splay(rt->rc,nxt(rt));

	s->lc=t,t->fa=s,s->upd(),s->fa->upd();

}

void tag(int x,int y){split(e+ls[x],e+rs[x])->lc->ppd(y);}

int n,m;

int main(){

//	freopen("testdata.in","r",stdin);

	n=read();

	for(R int i=2,x;i<=n;++i)x=read(),add(x,i);

	fp(i,1,n)a[i]=read();

	tim=1,dfs(1),build(rt,1,tim+1,e);

	m=read();

	char op;int x,y;

	while(m--){

		op=getop(),x=read();

		switch(op){

			case 'Q':print(get(x));break;

			case 'C':y=read(),move(x,y);break;

			case 'F':y=read(),tag(x,y);break;

		}

	}

	return Ot(),0;

}

巴特西

BZOJ3786: 星系探索（伪ETT）

题面

题解

最新文章

热门文章