jzoj3766&&bzoj4530题解

Dec 31, 2017 13:25 · 223 words · 2 minutes read 题解 jzoj bzoj LCT

有各种离线的做法,不过我感觉用lct在线做比较优雅。

这道题其实就是要求出子树大小,如果用lct来做的话,其实不需要考虑子树信息的维护,只需要能够维护整棵树的信息,查询的时候cut一下就好了。

lct上存在x->f为y,但y的左右儿子均不为x的情况,这个时候,我们称x为y的虚儿子。考虑对于每个splay的节点,额外维护一个域vir表示它的所有虚儿子的信息和,那就可以求出整棵树的信息了。而这个vir只会在access和link的时候被修改。

感觉不太会BB……可以看一下这篇题解。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
#define ele int
using namespace std;
#define maxn 100010
namespace LCT{
	struct node{
		ele s,vir;
		bool flip;
		node *f,*c[2];
		node(){
			s=1; vir=0;
			flip=false;
			f=c[0]=c[1]=NULL;
		}
	}np[maxn];
	inline bool splayroot(node *x){
		return (!x->f || (x->f->c[0]!=x && x->f->c[1]!=x));
	}
	inline void pushdown(node *x){
		if (x && x->flip){
			swap(x->c[0],x->c[1]);
			if (x->c[0]) x->c[0]->flip^=1;
			if (x->c[1]) x->c[1]->flip^=1;
			x->flip=false;
		}
	}
	inline void maintain(node *x){
		x->s=1+x->vir;
		if (x->c[0]) x->s+=x->c[0]->s;
		if (x->c[1]) x->s+=x->c[1]->s;
	}
	inline node* rotate(node *x,ele k){
		if (!x) return NULL;
		pushdown(x);
		node *y=x->c[k];
		if (!y) return x;
		pushdown(y);
		x->c[k]=y->c[k^1];
		if (y->c[k^1]) y->c[k^1]->f=x;
		y->c[k^1]=x;
		if (!splayroot(x))
			if (x->f->c[0]==x) x->f->c[0]=y;
			else x->f->c[1]=y;
		y->f=x->f; x->f=y;
		maintain(x); maintain(y);
		return y;
	}
	inline void splay(node *x){
		while (!splayroot(x)){
			pushdown(x->f);
			if (x->f->c[0]==x) rotate(x->f,0); else rotate(x->f,1);
		}
	}
	inline void access(node *x){
		node *p=NULL;
		while (x){
			splay(x); pushdown(x);
			if (x->c[1]) x->vir+=x->c[1]->s;
			if (p) p->f=x,x->vir-=p->s;
			x->c[1]=p; maintain(x);
			p=x; x=x->f;
		}
	}
	inline void mkroot(node *x){
		access(x); splay(x);
		x->flip^=1;
	}
	inline void link(node *x,node *y){
		mkroot(x); splay(x);
		access(y); splay(y);
		x->f=y; y->vir+=x->s;
		maintain(y);
	}
	inline void cut(node *x,node *y){
		mkroot(x);
		access(y); splay(y); pushdown(y);
		y->c[0]=NULL; x->f=NULL;
		maintain(y);
	}
	inline ele getsize(node *x){
		mkroot(x); splay(x);
		return x->s;
	}
};
using namespace LCT;
ele n,Q;
int main(){
	scanf("%d%d",&n,&Q);
	while (Q--){
		char op[5];
		ele x,y;
		scanf("%s%d%d",op,&x,&y); --x,--y;
		if (op[0]=='A') link(np+x,np+y);
		else{
			cut(np+x,np+y);
			printf("%lld\n",(long long)getsize(np+x)*getsize(np+y));
			link(np+x,np+y);
		}
	}
	return 0;
}