splay

cwy posted @ 2018年1月04日 14:03 in 板子 , 57 阅读

复习splay

http://codeforces.com/contest/38/submission/33897822

http://www.lydsy.com/JudgeOnline/problem.php?id=3786

#include<cstdio>
#include<cstring>
#include<iostream>
#include<stdlib.h>
#include<ctime>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define LL long long
#define FOR(i,a,b) for (int i=a;i<=b;i++)
#define FORD(i,a,b) for (int i=a;i>=b;i--)
using namespace std;
typedef pair<int,int> pa;
void getint(int &v){
    char ch,fu=0;
    for(ch='*'; (ch<'0'||ch>'9')&&ch!='-'; ch=getchar());
    if(ch=='-') fu=1, ch=getchar();
    for(v=0; ch>='0'&&ch<='9'; ch=getchar()) v=v*10+ch-'0';
    if(fu) v=-v;
}
struct node{
	int tp,d,fa;
	int ch[2],siz;
	LL s,v,tag;
}t[200010];
char s[55];
int rt,stk[500010],top,x,y,X,Y,nxt[500010],hed[500010],too[500010],nedge,n,m,a[100010],L[100010],R[100010],dfn,tot;
void ae(int x,int y){
	nxt[++nedge]=hed[x];
	hed[x]=nedge;
	too[nedge]=y;
}
bool isroot(int x){
	return (t[x].fa==0);
}
void dfs(int x,int l){
	L[x]=++dfn;
	t[L[x]].v=a[x];
	t[L[x]].tp=1;
	for (int i=hed[x];i;i=nxt[i]){
		int y=too[i];
		if (y==l) continue;
		dfs(y,x);
	}
	R[x]=++dfn;
	t[R[x]].v=-a[x];
	t[R[x]].tp=-1;
}
void TAG(int x,LL y){
	t[x].v+=t[x].tp*y;
	t[x].s+=t[x].d*y;
	t[x].tag+=y;
}
void pushup(int x){
	t[x].s=t[x].v+t[t[x].ch[0]].s+t[t[x].ch[1]].s;
	t[x].d=t[x].tp+t[t[x].ch[0]].d+t[t[x].ch[1]].d;
	t[x].siz=t[t[x].ch[0]].siz+t[t[x].ch[1]].siz+1;
}
void pushdown(int x){
	if (t[x].tag){
		if (t[x].ch[0]) TAG(t[x].ch[0],t[x].tag);
		if (t[x].ch[1]) TAG(t[x].ch[1],t[x].tag);
		t[x].tag=0;
	}
}
void debug(int x){
	pushdown(x);
	if (t[x].ch[0]) debug(t[x].ch[0]);
	printf("%lld ",t[x].v);
	if (t[x].ch[1]) debug(t[x].ch[1]);
}
int build(int l,int r,int fa){
	int m=l+r>>1;
	t[m].s=t[m].v;
	t[m].fa=fa;
	if (l<=m-1) t[m].ch[0]=build(l,m-1,m);
	if (m+1<=r) t[m].ch[1]=build(m+1,r,m);
	pushup(m);
	return m;
}
void rot(int x){
	int fa=t[x].fa;
	int gfa=t[fa].fa;
	int t1=(x!=t[fa].ch[0]);
	int t2=(fa!=t[gfa].ch[0]);
	int ch=t[x].ch[t1^1];
	if (!isroot(fa)) t[gfa].ch[t2]=x;
	t[ch].fa=fa;
	t[x].fa=gfa;
	t[x].ch[t1^1]=fa;
	t[fa].fa=x;
	t[fa].ch[t1]=ch;
	pushup(fa);
	pushup(x);
}
void splay(int x,int too){
	if (too==0) rt=x;
	if (too==-1) too=rt;
	stk[top=1]=x;
	int y=x;
	while (!isroot(y)) stk[++top]=t[y].fa,y=t[y].fa;
	FORD(rp,top,1) pushdown(stk[rp]);
	while (t[x].fa!=too){
		int fa=t[x].fa;
		int gfa=t[fa].fa;
		if (gfa!=too)
			x==t[fa].ch[0]^fa==t[gfa].ch[0]?rot(x):rot(fa);
		rot(x);
	}
}
int rnk(int x){
	splay(x,0);
//	debug(rt),puts("");
	return t[t[x].ch[0]].siz+1;
}
int fnd(int x,int k){
	if (x==-1) x=rt;
//	debug(rt),puts("");
	if (t[t[x].ch[0]].siz>=k) return fnd(t[x].ch[0],k);
	else if (k==t[t[x].ch[0]].siz+1) return x;
	else return fnd(t[x].ch[1],k-t[t[x].ch[0]].siz-1);
}
int main(){
//	freopen("t.in","r",stdin);
//	freopen("t.out","w",stdout);
	scanf("%d",&n);
	FOR(i,2,n){
		int t;
		getint(t);
		ae(t,i);
	}
	FOR(i,1,n) getint(a[i]);
	dfs(1,0);
	tot=dfn;
	rt=build(1,tot,0);
	t[tot+1].ch[1]=tot+2;
	t[tot+2].fa=tot+1;
	t[tot+2].ch[0]=rt;
	t[rt].fa=tot+2;
	rt=tot+1;
	scanf("%d",&m);
//	debug(rt),puts("");
	while (m--){
		scanf("%s",s);
	//	debug(rt),puts("");
		if (s[0]=='Q'){
			getint(x);
		//	debug(rt),puts("");
			int h=fnd(-1,rnk(L[x])+1);
		//	debug(rt),puts("");
			splay(h,0);
			pushdown(rt);
			printf("%lld\n",t[t[h].ch[0]].s);
		}
		else if (s[0]=='F'){
			getint(x),getint(y);
			X=fnd(-1,rnk(L[x])-1);
			Y=fnd(-1,rnk(R[x])+1);
			splay(X,0);
			splay(Y,-1);
		//	debug(rt),puts("");
			TAG(t[t[rt].ch[1]].ch[0],y);
			pushdown(rt);
			pushdown(t[rt].ch[1]);
			pushup(t[rt].ch[1]);
			pushup(rt);
		}
		else{
			getint(x),getint(y);
			X=fnd(-1,rnk(L[x])-1);
			Y=fnd(-1,rnk(R[x])+1);
			splay(X,0);
			splay(Y,-1);
		//	debug(rt),puts("");
			int w=t[t[rt].ch[1]].ch[0];
			t[t[w].fa].ch[0]=0;
			pushup(t[w].fa);
			pushup(rt);
		//	debug(rt),puts("");
			X=fnd(-1,rnk(L[y]));
			Y=fnd(-1,rnk(L[y])+1);
			splay(X,0);
			splay(Y,-1);
		//	debug(rt),puts("");
			t[Y].ch[0]=w;
			t[w].fa=Y;
			pushup(Y);
			pushup(X);
		}
	}
	return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter