夏晓光(loveJY)的博客

LCT练习题

不妨当做**[模板]动态图连通性(离线可过)**

线段树?那是什么神仙的东西?这种转移还能维护的???

所以考虑LCT

离线可过的想法还是很简单的,每条边在时间轴上都有一个存在时间,然后我们可以考虑线段树分治,然后并查集按秩合并可撤销之类的搞一搞

当然不可能,直接维护删除时间的最大生成树,然后你发现一个询问是否可行是一个树上查询最小值....

如果最小值大于当前询问就不行

调试已删除

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<map>
#define mkp(x,y) (make_pair(x,y))
using namespace std;
const int MAXN = 3e5 + 7;
const int inf = 1e9 + 7;
int n, m, tmp, T, Q;
map<pair<int, int>, int> mp;
int qwq[3][MAXN];
char s[20];
namespace LCT {
#define L ch[x][0]
#define R ch[x][1]
	static int ch[MAXN][2], f[MAXN], val[MAXN], minid[MAXN], st[MAXN];
	bool r[MAXN];
	inline bool nroot(int x) {
		return ch[f[x]][0] == x || ch[f[x]][1] == x;
	}
	inline void pushR(int x) {
		L ^= R ^= L ^= R;
		r[x] ^= 1;
	}
	inline void pushdown(int x) {
		if(r[x]) {
			if(L)pushR(L);
			if(R)pushR(R);
			r[x] = 0;
		}
	}
	inline void pushup(int x) {
		minid[x] = val[minid[L]] < val[minid[R]] ? minid[L] : minid[R];
		if(val[x] < val[minid[x]])minid[x] = x;
	}
	inline void rotate(int x) {
		int y = f[x], z = f[y], k = ch[y][1] == x, w = ch[x][!k];
		if(nroot(y))ch[z][ch[z][1] == y] = x;
		ch[x][!k] = y;
		ch[y][k] = w;
		if(w)f[w] = y;
		f[y] = x;
		f[x] = z;
		pushup(y);
	}
	inline void splay(int x) {
		int y = x, z = 0;
		st[++z] = y;
		while(nroot(y))st[++z] = y = f[y];
		while(z)pushdown(st[z--]);
		while(nroot(x)) {
			y = f[x];
			z = f[y];
			if(nroot(y))rotate((ch[y][0] == x) ^ (ch[z][0] == y) ? x : y);
			rotate(x);
		}
		pushup(x);
	}
	inline void access(int x) {
		for(int y = 0; x; x = f[y = x]) {
			splay(x);
			R = y;
			pushup(x);
		}
	}
	inline void makeroot(int x) {
		access(x);
		splay(x);
		pushR(x);
	}
	inline void split(int x, int y) {
		makeroot(x);
		access(y);
		splay(y);
	}
	inline int findroot(int x) {
		access(x);
		splay(x);
		while(L)pushdown(x), x = L;
		splay(x);
		return x;
	}
	inline void link(int x, int y) {
		split(x, y);
		f[x] = y;
	}
	inline void cut(int x, int y) {
		split(x, y);
		ch[y][0] = f[x] = 0;
		pushup(y);
	}
} using namespace LCT;


struct rec {
	int u, v, ed;
	bool operator<(const rec &x) {
		return ed > x.ed;
	}
} e[MAXN];

struct qry {
	int x, y, u, v, k;
} q[MAXN];

inline int nde(int x, int y) {
	if(!qwq[x][y])qwq[x][y] = ++T;
	return qwq[x][y];
}

int main() {
	scanf("%d", &n);
	while(1) {
		scanf("%s", s);
		if(s[0] == 'E')break;
		++Q;
		scanf("%d%d%d%d", &q[Q].x, &q[Q].y, &q[Q].u, &q[Q].v);
		int a = nde(q[Q].x, q[Q].y);
		int b = nde(q[Q].u, q[Q].v);
		if(a > b)a ^= b ^= a ^= b;
		if(s[0] == 'O') {
			++m;
			mp[mkp(a, b)] = m;
			e[m].u = a;
			e[m].v = b;
			q[Q].x = m;
			q[Q].k = 1;
		} else if(s[0] == 'C') {
			q[Q].x = mp[mkp(a, b)];
			e[q[Q].x].ed = Q;
			q[Q].k = 2;
		} else if(s[0] == 'A') {
			q[Q].x = a;
			q[Q].y = b;
		}
	}
	for(int i = 0; i <= T; ++i)val[i] = inf;
	for(int i = 1; i <= m; ++i) {
		if(!e[i].ed)val[i + T] = Q + 1, e[i].ed = Q + 1; //删除?不存在的
		else val[i + T] = e[i].ed;
	}
	for(int i = 1; i <= Q; ++i) {
		if(q[i].k == 0) {
			split(q[i].x, q[i].y);
			if(val[minid[q[i].y]] > i && findroot(q[i].x) == findroot(q[i].y))puts("Y");
			else puts("N");
		} else if(q[i].k == 1) {
			int I = q[i].x;
			split(e[I].u, e[I].v);
			if(findroot(e[I].u) != findroot(e[I].v)) {
				link(e[I].u, I + T);
				link(e[I].v, I + T);
			} else if(val[minid[e[I].v]] < e[I].ed) {
				int p = minid[e[I].v];
				cut(p, e[p - T].u);
				cut(p, e[p - T].v);
				val[p] = inf;
				link(e[I].u, I + T);
				link(e[I].v, I + T);
			}
		}
	}
	return 0;
}