【BZOJ1180】【CROATIAN2009】OTOCI

  裸的LCT。

  有事没事找道裸的LCT泄泄愤。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=300010;

struct LCT
{
	struct Node
	{
		Node *c[2],*p,*lcp;
		int v,sum;
		int tag_rev;
		int w() {return this==p->c[1];}
	}MEM[maxn],*ID[maxn],*Null;

	#define ls x->c[0]
	#define rs x->c[1]

	void Update(Node *x) {if (x==Null) return;x->sum=ls->sum+rs->sum+x->v;}
	void Mark_Rev(Node *x) {if (x==Null) return;swap(ls,rs);x->tag_rev^=1;}

	void Push_Down(Node *x)
	{
		if (x==Null) return;
		if (x->tag_rev)
		{
			Mark_Rev(ls);
			Mark_Rev(rs);
			x->tag_rev=0;
		}
	}

	void Rotate(Node *x)
	{
		Node *p=x->p;
		int w=x->w();
		Push_Down(p);Push_Down(x);
		x->lcp=p->lcp;p->lcp=Null;
		x->p=p->p;p->p->c[p->w()]=x;
		x->c[!w]->p=p;p->c[w]=x->c[!w];
		x->c[!w]=p;p->p=x;
		Update(p);
	}

	void Splay(Node *x)
	{
		Push_Down(x);
		while (x->p!=Null)
		{
			if (x->p->p==Null) {Rotate(x);break;}
			if (x->w()==x->p->w()) Rotate(x->p),Rotate(x);
				else Rotate(x),Rotate(x);
		}
		Update(x);
	}

	void Access(Node *x)
	{
		Node *v=Null,*pre=x;
		while (x!=Null)
		{
			Splay(x);
			rs->lcp=x;
			rs->p=Null;
			rs=v;
			v->lcp=Null;
			v->p=x;
			Update(x);
			v=x;x=x->lcp;
		}
		Splay(pre);
	}

	Node* Find_Root(Node *x)
	{
		Access(x);
		while (ls!=Null) x=ls;
		return x;
	}

	void Set_Root(Node *x)
	{
		Access(x);
		Mark_Rev(x);
	}

	void Init(int n,int *w)
	{
		Null=&MEM[0];
		for (int i=1;i<=n;i++) ID[i]=&MEM[i];
		for (int i=0;i<=n;i++) MEM[i].c[0]=MEM[i].c[1]=MEM[i].p=MEM[i].lcp=Null,MEM[i].v=MEM[i].sum=w[i];
	}

	bool Connected(int x,int y) {return Find_Root(ID[x])==Find_Root(ID[y]);}
	void Link(int x,int y) {Set_Root(ID[x]);Access(ID[y]);ID[x]->lcp=ID[y];Access(ID[x]);}
	void Change(int x,int y) {Access(ID[x]);ID[x]->v=y;Update(ID[x]);}
	int Sum(int x,int y) {Set_Root(ID[x]);Access(ID[y]);return ID[y]->sum;}
}T;

int w[maxn];
int n,q;

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&w[i]);
	T.Init(n,w);
	scanf("%d",&q);
	for (int i=1;i<=q;i++)
	{
		char ctr[20];
		int x,y;
		scanf("%s%d%d",ctr,&x,&y);
		if (ctr[0]=='b') if (T.Connected(x,y)) puts("no");else T.Link(x,y),puts("yes");
		if (ctr[0]=='p') T.Change(x,y);
		if (ctr[0]=='e') if (T.Connected(x,y)) printf("%d\n",T.Sum(x,y));else puts("impossible");
	}
	return 0;
}