题面

话说#122怎么做啊

题解

我的\(\mathrm{LCT}\)水平极差，连最小生成树都快忘了，赶紧复习一下

做法和这篇是一样的

这道题还可以练习线段树分治

还可以练习ETT

果然是道吼题

代码

LCT

#include<cstdio>

#include<cstring>

#include<cctype>

#include<algorithm>

#include<map>

#define RG register

#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)

#define clear(x, y) memset(x, y, sizeof(x))

inline int read()

{

	int data = 0, w = 1; char ch = getchar();

	while(ch != '-' && (!isdigit(ch))) ch = getchar();

	if(ch == '-') w = -1, ch = getchar();

	while(isdigit(ch)) data = data * 10 + (ch ^ 48), ch = getchar();

	return data * w;

}

const int maxn(505010), INF(0x3f3f3f3f);

struct edge { int opt, from, to, beg, end; } e[maxn];

int n, m, val[maxn], fa[maxn], son[2][maxn];

int stk[maxn], top, del[maxn], cnt, tim;

bool rev[maxn]; std::map<int, int> G[maxn];

inline bool isroot(int x) { return son[0][fa[x]] != x && son[1][fa[x]] != x; }

inline int getson(int x) { return son[1][fa[x]] == x; }

inline void update(int x)

{

	del[x] = x;

	if(val[del[x]] > val[del[son[0][x]]]) del[x] = del[son[0][x]];

	if(val[del[x]] > val[del[son[1][x]]]) del[x] = del[son[1][x]];

}

inline void pushdown(int x)

{

	if(!rev[x]) return;

	rev[son[0][x]] ^= 1;

	rev[son[1][x]] ^= 1;

	rev[x] = 0, std::swap(son[0][x], son[1][x]);

}

inline void rotate(int x)

{

	int f = fa[x], g = fa[f], l = getson(x), r = l ^ 1;

	if(!isroot(f)) son[getson(f)][g] = x;

	fa[x] = g, fa[f] = x, fa[son[r][x]] = f;

	son[l][f] = son[r][x], son[r][x] = f;

	update(f); update(x);

}

void splay(int x)

{

	stk[top = 1] = x;

	for(RG int i = x; !isroot(i); i = fa[i]) stk[++top] = fa[i];

	for(RG int i = top; i; i--) pushdown(stk[i]);

	for(; !isroot(x); rotate(x)) if(!isroot(fa[x]))

		rotate(getson(fa[x]) ^ getson(x) ? x : fa[x]);

}

void access(int x)

{

	for(RG int t = 0; x; t = x, x = fa[x])

		splay(x), son[1][x] = t, update(x);

}

int find(int x) { access(x); splay(x); while(son[0][x]) x = son[0][x]; return x; }

inline void makeroot(int x) { access(x); splay(x); rev[x] ^= 1; }

inline void split(int x, int y) { makeroot(x); access(y); splay(y); }

inline void link(int x, int y) { makeroot(x); fa[x] = y; }

inline void cut(int x, int y) { split(x, y); son[0][y] = fa[x] = 0; update(y); }

int main()

{

	cnt = n = read(), m = read();

	for(RG int i = 1; i <= m; i++)

	{

		int opt = read(), x = read(), y = read();

		if(x > y) std::swap(x, y);

		++tim;

		if(opt == 0) e[G[x][y] = tim].end = INF;

		if(opt == 1) e[G[x][y]].end = tim;

		e[tim].beg = tim, e[tim].opt = opt, e[tim].from = x, e[tim].to = y;

	}

	for(RG int i = 0; i <= cnt; i++) val[i] = INF;

	for(RG int i = 1; i <= tim; i++)

	{

		int x1 = e[i].from, x2 = e[i].to;

		if(e[i].opt == 0)

		{

			if(x1 == x2) continue;

			if(find(x1) == find(x2))

			{

				split(x1, x2); int d = del[x2];

				if(val[d] >= e[i].end) continue;

				else cut(x1, d), cut(x2, d);

				val[++cnt] = e[i].end;

				link(x1, cnt), link(x2, cnt);

			}

			else val[++cnt] = e[i].end, link(x1, cnt), link(x2, cnt);

		}

		if(e[i].opt == 1)

		{

			if(find(x1) == find(x2))

			{

				split(x1, x2); int d = del[x2];

				if(val[d] > e[i].beg) continue;

				cut(x1, d), cut(x2, d);

			}

		}

		if(e[i].opt == 2) puts(find(x1) == find(x2) ? "Y" : "N");

	}

	return 0;

}

线段树分治

咕咕咕