如果你用 SATT 来写 LCT 板子（
2025-05-22 20:17:08
发布于：山东
23阅读
0回复
0点赞
下次更新应该是把 Sone1 调过的时候（）
// #pragma GCC optimize(3, "Ofast", "inline", "unroll-loops")
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 500010;
int n, m;
template<const int NN = N>
struct SATT
{
int root, idx;
vector<int> adj[NN];
queue<int> pool;
struct Tree
{
int sum[3], siz[3], val, fa, son[3], tag[2], rev;
Tree()
{
val = fa = rev = 0;
memset(sum, 0, sizeof sum);
memset(siz, 0, sizeof siz);
memset(son, 0, sizeof son);
memset(tag, 0, sizeof tag);
}
} tree[NN];
int newnode()
{
int nw;
if (pool.size())
{
nw = pool.front();
pool.pop();
}
else
nw = ++idx;
tree[nw] = Tree();
return nw;
}
void pushup(int rt)
{
tree[rt].sum[0] = tree[tree[rt].son[0]].sum[0] ^ tree[tree[rt].son[1]].sum[0] ^ tree[rt].val;
tree[rt].sum[1] = tree[tree[rt].son[2]].sum[2] ^ tree[rt].val;
tree[rt].sum[2] = tree[tree[rt].son[0]].sum[2] ^ tree[tree[rt].son[1]].sum[2] ^ tree[rt].sum[1];
tree[rt].siz[0] = tree[tree[rt].son[0]].siz[0] + tree[tree[rt].son[1]].siz[0];
tree[rt].siz[1] = tree[tree[rt].son[1]].siz[2];
if (rt <= n)
{
++tree[rt].siz[0];
++tree[rt].siz[1];
}
tree[rt].siz[2] = tree[tree[rt].son[0]].siz[2] + tree[tree[rt].son[1]].siz[2] + tree[rt].siz[1];
}
inline int isroot(int rt)
{
return tree[tree[rt].fa].son[0] == rt || tree[tree[rt].fa].son[1] == rt;
}
void pushadd0(int rt, int val)
{
if (!rt)
return;
tree[rt].tag[0] ^= val;
if (rt <= n)
tree[rt].val ^= val;
if (tree[rt].siz[0] & 1)
{
tree[rt].sum[0] ^= val;
tree[rt].sum[2] ^= val;
}
tree[rt].sum[1] ^= val;
}
void pushadd1(int rt, int val)
{
if (!rt)
return;
tree[rt].tag[1] ^= val;
if (rt <= n)
tree[rt].val ^= val;
if (tree[rt].siz[0] & 1)
tree[rt].sum[0] ^= val;
if (tree[rt].siz[1] & 1)
tree[rt].sum[1] ^= val;
if (tree[rt].siz[2] & 1)
tree[rt].sum[2] ^= val;
}
void pushrev(int rt)
{
if (!rt)
return;
tree[rt].rev ^= 1;
swap(tree[rt].son[0], tree[rt].son[1]);
}
void pushdown(int rt)
{
if (tree[rt].rev)
{
pushrev(tree[rt].son[0]);
pushrev(tree[rt].son[1]);
tree[rt].rev = 0;
}
if (tree[rt].tag[0])
{
pushadd0(tree[rt].son[0], tree[rt].tag[0]);
pushadd0(tree[rt].son[1], tree[rt].tag[0]);
tree[rt].tag[0] = 0;
}
if (tree[rt].tag[1])
{
pushadd1(tree[rt].son[0], tree[rt].tag[1]);
pushadd1(tree[rt].son[1], tree[rt].tag[1]);
pushadd1(tree[rt].son[2], tree[rt].tag[1]);
tree[rt].tag[1] = 0;
}
}
void pushlnk(int rt)
{
vector<int> v = {rt};
while (isroot(rt))
{
rt = tree[rt].fa;
v.emplace_back(rt);
}
reverse(v.begin(), v.end());
for (int &i : v)
pushdown(i);
}
void pushroot(int rt)
{
vector<int> v;
while (rt)
{
v.emplace_back(rt);
rt = tree[rt].fa;
}
reverse(v.begin(), v.end());
for (int &i : v)
pushdown(i);
}
void rotate(int x)
{
int y = tree[x].fa, z = tree[y].fa;
int o = (x == tree[y].son[1]) ? 1 : 0, oo = tree[x].son[o ^ 1];
if (tree[z].son[0] == y)
tree[z].son[0] = x;
else if (tree[z].son[1] == y)
tree[z].son[1] = x;
else if (tree[z].son[2] == y)
tree[z].son[2] = x;
tree[x].son[o ^ 1] = y;
tree[y].son[o] = oo;
tree[oo].fa = y;
tree[y].fa = x;
tree[x].fa = z;
pushup(y);
pushup(x);
}
void splay(int rt)
{
pushlnk(rt);
while (isroot(rt))
{
int o = tree[rt].fa, oo = tree[o].fa;
if (isroot(o))
{
int id = o;
if (tree[oo].son[0] == o && tree[o].son[0] != rt)
id = rt;
else if (tree[oo].son[0] != o && tree[o].son[0] == rt)
id = rt;
rotate(id);
}
rotate(rt);
}
}
void ins(int x, int y)
{
tree[x].siz[1] += tree[y].siz[2];
tree[x].siz[2] += tree[y].siz[2];
tree[x].sum[1] ^= tree[y].sum[2];
tree[x].sum[2] ^= tree[y].sum[2];
int id = newnode();
tree[id].son[2] = y;
tree[y].fa = id;
tree[id].siz[1] = tree[id].siz[2] = tree[y].siz[2];
tree[id].sum[1] = tree[id].sum[2] = tree[y].sum[2];
if (tree[x].son[2])
{
tree[tree[x].son[2]].fa = id;
tree[id].son[0] = tree[x].son[2];
}
tree[x].son[2] = id;
tree[id].fa = x;
pushup(id);
pushup(x);
}
void del(int x, int y)
{
tree[x].siz[1] -= tree[y].siz[1];
tree[x].siz[2] -= tree[y].siz[1];
tree[x].sum[1] ^= tree[y].sum[1];
tree[x].sum[2] ^= tree[y].sum[1];
splay(y);
if (!tree[y].son[0] && !tree[y].son[1])
{
tree[x].son[2] = 0;
pushup(x);
pool.emplace(y);
return;
}
else if (!tree[y].son[0])
{
tree[tree[y].son[1]].fa = x;
tree[x].son[2] = tree[y].son[1];
pushup(x);
pool.emplace(y);
return;
}
else if (!tree[y].son[1])
{
tree[tree[y].son[0]].fa = x;
tree[x].son[2] = tree[y].son[0];
pushup(x);
pool.emplace(y);
return;
}
else
{
int z = tree[y].son[0];
tree[y].son[0] = tree[z].fa = 0;
while (tree[z].son[1])
z = tree[z].son[1];
splay(z);
tree[z].son[1] = tree[y].son[1];
tree[tree[y].son[1]].fa = z;
tree[z].fa = x;
tree[x].son[2] = z;
pushup(z);
pushup(x);
pool.emplace(y);
return;
}
}
void access(int rt)
{
pushroot(rt);
splay(rt);
if (tree[rt].son[1])
ins(rt, tree[rt].son[1]);
tree[rt].son[1] = 0;
pushup(rt);
while (1)
{
splay(rt);
int o = tree[rt].fa;
if (!o)
break;
splay(o);
int oo = tree[o].fa;
splay(oo);
del(oo, o);
if (tree[oo].son[1])
ins(oo, tree[oo].son[1]);
tree[oo].son[1] = rt;
tree[rt].fa = oo;
pushup(oo);
rt = oo;
}
}
void makeroot(int rt)
{
access(rt);
splay(rt);
pushrev(rt);
}
int find(int rt)
{
access(rt);
splay(rt);
while (tree[rt].son[0])
{
pushdown(rt);
rt = tree[rt].son[0];
}
splay(rt);
return rt;
}
int link(int x, int y)
{
makeroot(x);
if (x == find(y))
return 0;
splay(y);
ins(y, x);
pushup(y);
return 1;
}
int cut(int x, int y)
{
makeroot(x);
access(y);
splay(y);
if (tree[y].son[0] != x || tree[x].son[1])
return 0;
tree[x].fa = tree[y].son[0] = 0;
pushup(y);
return 1;
}
inline void split(int x, int y)
{
makeroot(x);
access(y);
splay(y);
}
inline int treequery(int x)
{
makeroot(root);
access(x);
return tree[x].sum[1];
}
inline int linkquery(int x, int y)
{
split(x, y);
return tree[y].sum[0];
}
void treemodify(int x, int y)
{
makeroot(root);
access(x);
splay(x);
tree[x].val ^= y;
if (tree[x].son[1])
pushadd1(tree[x].son[1], y);
if (tree[x].son[2])
pushadd1(tree[x].son[2], y);
pushup(x);
}
inline void linkmodify(int x, int y, int z)
{
split(x, y);
pushadd0(y, z);
pushup(x);
}
void change(int x, int y)
{
access(x);
splay(x);
tree[x].val = y;
pushup(x);
}
void chgfa(int x, int y)
{
if (x == root)
return;
makeroot(root);
access(x);
splay(x);
int o = tree[x].son[0];
while (tree[o].son[1])
{
pushdown(o);
o = tree[o].son[1];
}
cut(o, x);
makeroot(x);
if (find(y) != x)
link(y, x);
else
link(o, x);
}
void dfs(int u, int fa)
{
for (int &v : adj[u])
if (v != fa)
{
dfs(v, u);
ins(u, v);
}
pushup(u);
}
} ; SATT satt;
signed main()
{
cin.tie(0)->sync_with_stdio(false);
cin >> n >> m;
satt.idx = n;
for (int i = 1; i <= n; ++i)
{
int x;
cin >> x;
satt.tree[i].sum[0] = satt.tree[i].sum[1] = satt.tree[i].sum[2] = x;
satt.tree[i].val = x;
satt.tree[i].siz[0] = satt.tree[i].siz[1] = satt.tree[i].siz[2] = 1;
}
while (m--)
{
int o;
cin >> o;
if (!o)
{
int a, b;
cin >> a >> b;
cout << satt.linkquery(a, b) << '\n';
}
else if (o == 1)
{
int x, y;
cin >> x >> y;
satt.link(x, y);
}
else if (o == 2)
{
int x, y;
cin >> x >> y;
satt.cut(x, y);
}
else
{
int x, y;
cin >> x >> y;
satt.change(x, y);
}
}
return 0;
}
/*
5 6
1 2 3 4 5
3 1 5 3 0
5 1
6 2 3
1 3 1
2 1 5 3
3 3
4 2 4
*/
有帮助，赞一个