LuoguP4219 [BJOI2014]大融合(LCT)

早上考试想用\(LCT\)维护联通块\(size\)，现在才发现\(LCT\)的\(size\)有虚实之分

\(Link\)与\(Acess\)中虚实变,干他丫的

\(Splay\)中只是相对关系，没有虚实变，因此不搞它
#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#define R(a,b,c) for(register int a = (b); a <= (c); ++a)

#define nR(a,b,c) for(register int a = (b); a >= (c); --a)

#define Fill(a,b) memset(a, b, sizeof(a))

#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))

#define ON_DEBUGG

#ifdef ON_DEBUGG

#define D_e_Line printf("-----------\n")

#define D_e(x) std::cout << (#x) << " : " <<x << "\n"

#define FileOpen() freopen("in.txt", "r", stdin)

#define FileSave() freopen("out.txt", "w", stdout)

#define Pause() system("pause")

#include <ctime>

#define TIME() fprintf(stderr, "\nTIME :　%.3lfms\n", clock() * 1000.0 / CLOCKS_PER_SEC)

#else

#define D_e_Line ;

#define D_e(x) ;

#define FileOpen() ;

#define FilSave ;

#define Pause() ;

#define TIME() ;

#endif

struct ios {

	template<typename ATP> ios& operator >> (ATP &x) {

		x = 0; int f = 1; char c;

		for(c = getchar(); c < '0' || c > '9'; c = getchar()) if(c == '-') f = -1;

		while(c >= '0' && c <= '9') x = x * 10 + (c ^ '0'), c = getchar();

		x *= f;

		return *this;

	}

}io;

using namespace std;

template<typename ATP> inline ATP Min(ATP a, ATP b) {

	return a < b ? a : b;

}

template<typename ATP> inline ATP Max(ATP a, ATP b) {

	return a > b ? a : b;

}

template<typename ATP> inline ATP Abs(ATP a) {

	return a < 0 ? -a : a;

}

const int N = 1e5 + 7;

struct LCT {

	int ch[2], fa, siz, sz; // siz : true edge, sz : virtual edge

	bool rev;

} t[N];

#define ls t[u].ch[0]

#define rs t[u].ch[1]

inline int Ident(int &u) {

	return t[t[u].fa].ch[1] == u;

}

inline bool IsRoot(int &u) {

	return t[t[u].fa].ch[0] != u && t[t[u].fa].ch[1] != u;

}

inline void Pushup(int &u) {

	if(u) t[u].siz = t[ls].siz + t[rs].siz + t[u].sz + 1;

	// left + right + virtual + self

}

inline void Pushrev(int u) {

	Swap(ls, rs);

	t[u].rev ^= 1;

}

inline void Pushdown(int u) {

	if(!t[u].rev) return;

	if(ls) Pushrev(ls);

	if(rs) Pushrev(rs);

	t[u].rev = 0;

}

inline void Rotate(int x) {

	int y = t[x].fa, z = t[y].fa, k = Ident(x);

	t[x].fa = z; if(!IsRoot(y)) t[z].ch[Ident(y)] = x;

	t[y].ch[k] = t[x].ch[k ^ 1], t[t[x].ch[k ^ 1]].fa = y;

	t[x].ch[k ^ 1] = y, t[y].fa = x;

	Pushup(y), Pushup(x);

}

int sta[N], top;

inline void Splay(int u) {

	int x = u;

	while(!IsRoot(u)){

		sta[++top] = u;

		u = t[u].fa;

	}

	sta[++top] = u;

	while(top) Pushdown(sta[top--]);

	while(!IsRoot(x)){

		int y = t[x].fa;

		if(!IsRoot(y)){

			Ident(x) == Ident(y) ? Rotate(y) : Rotate(x);

		}

		Rotate(x);

	}

	Pushup(x);

}

inline void Access(int u) {

	for(register int v = 0; u; v = u, u = t[u].fa){

		Splay(u);

		t[u].sz += t[rs].siz - t[v].siz;

		t[u].ch[1] = v;

		Pushup(u);

	}

}

inline void MakeRoot(int u) {

	Access(u);

	Splay(u);

	Pushrev(u);

}

inline void Split(int u, int v) {

	MakeRoot(u);

	Access(v);

	Splay(v);

}

inline void Link(int u, int v) {

	Split(u, v);

	t[u].fa = v;

	t[v].sz += t[u].siz;

}

inline long long Query(int u, int v) {

	Split(u, v);

	return 1ll * (t[u].sz + 1) * (t[v].sz + 1);

}

//inline void Link(int u, int v) {

//	MakeRoot(u);

//	MakeRoot(v);

//	t[u].fa = v;

//	t[v].sz += t[u].siz;

//	Pushup(v);

//}

//inline long long Query(int u, int v) {

//	MakeRoot(u);

//	MakeRoot(v);

//	return 1ll * (t[u].sz + 1) * (t[v].sz + 1);

//}

char opt[13];

int main() {

	int n, m;

	io >> n >> m;

	R(i,1,n){

		t[i].siz = 1;

		t[i].sz = 0;

	}

	while(m--){

		scanf("%s", opt + 1);

		int x, y;

		io >> x >> y;

		if(opt[1] == 'A'){

			Link(x, y);

		}

		else{

			printf("%lld\n", Query(x, y));

		}

	}

	return 0;

}
巴特西

LuoguP4219 [BJOI2014]大融合(LCT)

最新文章

热门文章
