萌新求助LCT,TLE on #8#9#11
查看原帖
萌新求助LCT,TLE on #8#9#11
551861
strcmp楼主2022/3/29 17:25

rt,请问是哪里写挂了?

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int N = 4e5 + 10;
struct node {
	int ch[2], fa;
	ll val, ans;
	bool tage;
}spl[N];
#define ls(x) (spl[x].ch[0])
#define rs(x) (spl[x].ch[1])
#define fa(x) (spl[x].fa)
#define val(x) (spl[x].val)
#define ans(x) (spl[x].ans)
#define indnt(x) (x == rs(fa(x)))
#define ntrt(x) (x == ls(fa(x)) || x == rs(fa(x)))
#define upd(x) (ans(x) = ans(ls(x)) ^ ans(rs(x)) ^ val(x))
#define rvs(x) swap(ls(x), rs(x)), spl[x].tage ^= 1
inline void pushdw(int x) {
	if (spl[x].tage) {
		if (ls(x))rvs(ls(x));
		if (rs(x))rvs(rs(x));
	}
	spl[x].tage = 0;
}
void pushall(int x) {
	if (fa(x))pushall(fa(x));
	pushdw(x);
}
inline void rtt(int x) {
	int f = fa(x), ff = fa(f), d = indnt(x);
	if (ntrt(f))spl[ff].ch[indnt(f)] = x;
	fa(x) = ff;
	spl[f].ch[d] = spl[x].ch[d ^ 1];
	fa(spl[x].ch[d ^ 1]) = f;
	spl[x].ch[d ^ 1] = f; fa(f) = x;
	upd(f), upd(x);
}
inline void splaying(int x) {
	pushall(x);
	int f, ff;
	while (ntrt(x)) {
		f = fa(x), ff = fa(f);
		if (ntrt(f))indnt(x) ^ indnt(f) ? rtt(x) : rtt(f);
		rtt(x);
	}
}
inline void access(int x) {
	for (int y = 0; x; x = fa(y = x)) {
		splaying(x);
		rs(x) = y;
		upd(x);
	}
}
inline void makert(int x) {
	access(x);
	splaying(x);
	rvs(x);
}
inline int findrt(int x) {
	access(x);
	splaying(x);
	while (ls(x))pushdw(x), x = ls(x);
	splaying(x);
	return x;
}
inline void link(int x, int y) {
	makert(x);
	if (findrt(y) != x)fa(x) = y;
}
inline void cut(int x, int y) {
	makert(x);
	if (findrt(y) != x || y != rs(x) || ls(y))return;
	rs(x) = fa(y) = 0;
	upd(x);
}
inline void split(int x, int y) {
	makert(x);
	access(y);
	splaying(y);
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(); cout.tie();
	int n, m, q, x, y;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)cin >> spl[i].val;
	while (m--) {
		cin >> q >> x >> y;
		if (q == 0)split(x, y), cout << spl[y].ans << endl;
		else if (q == 1)link(x, y);
		else if (q == 2)cut(x, y);
		else {
			splaying(x);
			spl[x].val = y;
			upd(x);
		}
	}
	return 0;
}
2022/3/29 17:25
加载中...