loj122题解

Dec 31, 2017 13:36 · 403 words · 2 minutes read 题解 loj LCT 动态图

写+调了7h+,终于成为AC此题的第四个人+此题目前最短代码+此题目前最慢代码……

去CA的博客上翻WC2015 xyz的课件来看吧……虽然看懂了但是完全不想写题解……太复杂了……

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include <queue>
#define ele int
using namespace std;
#define maxn 5010
#define maxm 500010
#define maxk 15
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; }
	};
	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 bool test(node *x,node *y){
		mkroot(x);
		access(y); splay(y); pushdown(y);
		while (y->c[0]) pushdown(y=y->c[0]);
		return x==y;
	}
};
using namespace LCT;
struct DG{
	set<ele> f[maxk][maxn],g[maxk][maxn];
	node np[maxk][maxn];
	queue<ele> Q;
	inline bool test(ele x,ele y){
		return LCT::test(np[maxk-1]+x,np[maxk-1]+y);
	}
	inline void link(ele x,ele y){
		if (!test(x,y)){
			f[maxk-1][x].insert(y);
			f[maxk-1][y].insert(x);
			LCT::link(np[maxk-1]+x,np[maxk-1]+y);
		}
		else{
			g[maxk-1][x].insert(y);
			g[maxk-1][y].insert(x);
		}
	}
	inline ele getsize(ele i,ele x){
		mkroot(np[i]+x); splay(np[i]+x);
		return np[i][x].s;
	}
	void find_replace(ele i,ele p,ele x,ele y,bool &flag){
		for (int j=i-1; ~j; --j){
			for (set<ele>::iterator it=f[j][x].begin(); it!=f[j][x].end(); ++it)
				if (*it!=p) find_replace(i,x,*it,y,flag);
		}
		for (set<ele>::iterator it=f[i][x].begin(); it!=f[i][x].end();){
			ele v=*it;
			f[i][x].erase(it++);
			f[i][v].erase(x);
			if (i){
				f[i-1][x].insert(v);
				f[i-1][v].insert(x);
				LCT::link(np[i-1]+x,np[i-1]+v);
			}
			find_replace(i,x,v,y,flag);
		}
		for (set<ele>::iterator it=g[i][x].begin(); it!=g[i][x].end() && !flag;){
			ele v=*it;
			g[i][x].erase(it++);
			g[i][v].erase(x);
			if (LCT::test(np[i]+v,np[i]+y)){
				f[i][x].insert(v); f[i][v].insert(x);
				for (int j=i; j<maxk; ++j)
					LCT::link(np[j]+x,np[j]+v);
				flag=true;
			}
			else if (i){
				g[i-1][x].insert(v);
				g[i-1][v].insert(x);
			}
		}
	}
	inline void cut(ele x,ele y){
		ele L;
		for (int i=maxk-1; ~i; --i)
			if (g[i][x].count(y)){
				g[i][x].erase(y);
				g[i][y].erase(x);
				return;
			}
			else if (f[i][x].count(y)){
				L=i;
				f[i][x].erase(y);
				f[i][y].erase(x);
				break;
			}
		for (int i=L; i<maxk; ++i) LCT::cut(np[i]+x,np[i]+y);
		bool flag=false;
		for (int i=L; i<maxk; ++i){
			if (getsize(i,x)>getsize(i,y)) swap(x,y);
			find_replace(i,-1,x,y,flag);
			if (flag) break;
		}
	}
};
ele n,m;
DG g;
int main(){
	scanf("%d%d",&n,&m);
	ele lastans=0;
	while (m--){
		ele op,x,y;
		scanf("%d%d%d",&op,&x,&y);
		x^=lastans; y^=lastans;
		if (op==0) g.link(x-1,y-1);
		else if (op==1) g.cut(x-1,y-1);
		else{
			bool ans=g.test(x-1,y-1);
			lastans=ans?x:y;
			puts(ans?"Y":"N");
		}
	}
	return 0;
}