BZOJ-3786: 星系探索 splay+dfs序

[文章目录]

Description

给定一个n节点有点权的树,有以下m次操作。

1.一个节点的子树上(包括自己)的所有节点点权加一个定值.

2.移动子树到另一个节点下方。

3.查询某一结点到根节点的路径上的点权和

(n<=100000,m<=300000)

有个叫dfs序的东西,本题要用到。

先想到要维护点权加和,还要有移动。splay啊。但是维护的东西要使得能求出区间和,就是点到根节点的路径上的点权和。

选择维护dfs的出栈入栈序,出栈权值为负,那么点到根节点的路径的点权和就是概数列的前缀和(好玄学的东西,想想就觉得好神奇)。然后一个节点的子树恰好也在一个连续区间里,就是时间戳在节点的入栈出栈内的点。移动的话直接移动就好了,移到该区间的入站时间戳的后边。不要忘了修改fa。

另外加值的时候由于要一下更新好该节点的所有参数,所以维护一个系数的和,这样的话,该节点子树点权和+的就是系数的和*增加的值。

不同的一点就是写了一个找前面元素指针和后面元素指针的函数(由于只能获得闭区间的端点指针),还有就是由于要push_down,所以从一个节点直接向上爬到根,放到一个麻袋里,然后一个个取出下传。

还有什么long long的东西

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define N 101000
using namespace std;
LL n,m,k1,k2;
char st[20];
LL head[N],to[N],nxt[N],cnt;
LL val[N];
void add_edge(LL x,LL y)
{
	to[++cnt]=y;
	nxt[cnt]=head[x];
	head[x]=cnt;
}
struct node
{
	node *fa,*c[2];
	LL flag;
	LL add,val,sum,fsum;//系数的和
	node(LL x,LL y);
	void push_up();
	void push_down();
	void all_add(LL x);
}*null=new node(0,0),*root,*a[201000],*fro;
LL in[N],out[N],tot,top;//in[]为入站时间戳,out[]为出栈时间戳
node *zan[N];
void node :: all_add(LL x)
{
	sum+=x*fsum; 
	val+=x; //这里智障的一开始写成x*flag了。
	add+=x;
}
node :: node(LL x,LL y)
{
	fa=c[0]=c[1]=null;
	val=x;
	fsum=flag=y;
	add=0;
	sum=y*x;
}
void node::push_up()
{
	fsum=c[0]->fsum+c[1]->fsum+flag;
	sum=c[0]->sum+c[1]->sum+val*flag;
}
void node::push_down()
{
	if(add)
	{
		if(c[0]!=null) c[0]->all_add(add);
		if(c[1]!=null) c[1]->all_add(add);
		add=0; 
	}
}
node *front(node *x)//前驱指针
{
	if(x->c[0]!=null)
	{
		x=x->c[0];
		while(x->c[1]!=null) x=x->c[1];
		return x;
	}
	while(x==x->fa->c[0]) x=x->fa;
	return x->fa;
}
node *after(node *x)//后继指针
{
	if(x->c[1]!=null)
	{
		x=x->c[1];
		while(x->c[0]!=null) x=x->c[0];
		return x;
	}
	while(x==x->fa->c[1]) x=x->fa;
	return x->fa;
}
node * build(LL l,LL r)
{
	if(l>r) return null;
	LL mid=l+r>>1; node *re=a[mid];
	re->c[0]=build(l,mid-1);re->c[1]=build(mid+1,r);
	re->c[0]->fa=re;re->c[1]->fa=re;
	re->push_up();return re;
}
void initialize()
{
	fro=root=new node(0,0);
	root->c[1]=new node(0,0);
	root->c[1]->fa=root;
	root->c[1]->c[0]=build(1,tot);
	root->c[1]->c[0]->fa=root->c[1];
	root->c[1]->push_up();
	root->push_up();
}
void rotate(node *x)
{
	node *y=x->fa;LL l=(x==y->c[1]),r=l^1;
	y->c[l]=x->c[r];x->c[r]->fa=y;
	x->c[r]=y;x->fa=y->fa;
	if(y==y->fa->c[l]) y->fa->c[l]=x;
	else y->fa->c[r]=x;
	y->fa=x;y->push_up();x->push_up();
	if(y==root) root=x;
}
LL read()
{
	char ch=getchar();LL re=0;
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9')
		re=(re<<1)+(re<<3)+ch-'0',ch=getchar();
	return re;
}
void dfs(LL x)//dfs出栈入栈序
{
	a[++tot]=new node(val[x],1);in[x]=tot;//入 系数为1
	for(LL i=head[x];i;i=nxt[i]) dfs(to[i]);
	out[x]=++tot; a[tot]=new node(val[x],-1);//出 系数为 -1
}
void dfs_check(node *x)
{
	if(x==null) return ;
	x->push_down();
	dfs_check(x->c[0]);
	printf("%lld %lld ls %lld rs %lld fsum %lld sum %lld add %lld\n",x->val,x->flag,x->c[0]->val,x->c[1]->val,x->fsum,x->sum,x->add);
	dfs_check(x->c[1]);
}
void splay(node *x,node *tar)
{
	while(1)
	{
		node *y=x->fa,*z=y->fa;
		if(y==tar) break;
		if(z==tar){rotate(x);break;}
		if((x==y->c[0])^(y==z->c[0])==0) rotate(y);
		else rotate(x); rotate(x);
	}
}

void find(node *x,node *z)//自底向上
{
	top=0;
	while(x!=null) {zan[++top]=x;x=x->fa;}
	while(top) {zan[top]->push_down();top--;}
	splay(zan[1],z);
}
int main()
{
	n=read();
	for(LL x,i=2;i<=n;i++){x=read();add_edge(x,i);}
	for(LL i=1;i<=n;i++) val[i]=read();
	dfs(1);
	initialize();
	//dfs_check(root);
	m=read();
	while(m--)
	{
		scanf("%s",st);k1=read();
		switch(st[0])
		{
			case 'Q':
			{
				find(fro,null);
				find(after(a[in[k1]]),root);
				//dfs_check(root);
				printf("%lld\n",root->c[1]->c[0]->sum);
				break;
			}
			case 'F':
			{
				k2=read();
				find(front(a[in[k1]]),null);
				find(after(a[out[k1]]),root);
				root->c[1]->c[0]->all_add(k2);
				root->c[1]->push_up();
				root->push_up();
				break;
			}
			case 'C':
			{
				k2=read();
				find(front(a[in[k1]]),null);
				find(after(a[out[k1]]),root);
				node *tmp=root->c[1]->c[0];
				root->c[1]->c[0]=null;
				root->c[1]->push_up();root->push_up();
				find(a[in[k2]],null);
				find(after(a[in[k2]]),root);
				root->c[1]->c[0]=tmp;
				tmp->fa=root->c[1];//重中之重
				root->c[1]->push_up();root->push_up();
				break;
			}
		}
		//dfs_check(root);
	}
	return 0;
}

 

发表评论

邮箱地址不会被公开。 必填项已用*标注