LCT 模板题;
话说 xor 和的意思是所有数 xor 一下;
- #include < iostream > #include < cstdio > #include < cstring > #include < string > #include < cmath > #include < cstdlib > #include < ctime > #include < algorithm > using namespace std;#define mid((l + r) >> 1)#define LL long long#define FILE "dealing"#define up(i, j, n) for (LL i = (j); i <= (n); i++)#define pii pair < int,
- int > int read() {
- int x = 0,
- f = 1,
- ch = getchar();
- while (ch < '0' || ch > '9') {
- if (ch == ' - ') f = -1;
- ch = getchar();
- }
- while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + ch - '0',
- ch = getchar();
- return f * x;
- }
- const int maxn = 306000,
- inf = 100000000,
- mod = 998244353;
- int n,
- m,
- cnt;
- int c[maxn][2],
- fa[maxn],
- rev[maxn],
- w[maxn],
- v[maxn],
- sum[maxn];
- void reve(int x) {
- rev[x] ^= 1,
- swap(c[x][0], c[x][1]);
- }
- void updata(int x) {
- sum[x] = sum[c[x][1]] ^ sum[c[x][0]] ^ v[x];
- }
- void pushdown(int x) {
- if (rev[x]) rev[x] ^= 1,
- reve(c[x][1]),
- reve(c[x][0]);
- }
- bool isroot(int x) {
- return c[fa[x]][1] != x && c[fa[x]][0] != x;
- }
- void rotate(int x) {
- int y = fa[x],
- z = fa[y],
- d = c[y][1] == x;
- if (!isroot(y)) c[z][c[z][1] == y] = x;
- fa[y] = x,
- fa[x] = z,
- fa[c[x][d ^ 1]] = y;
- c[y][d] = c[x][d ^ 1],
- c[x][d ^ 1] = y;
- updata(y);
- updata(x);
- }
- int q[maxn],
- top = 0;
- void splay(int x) {
- q[++top] = x;
- for (int i = x; ! isroot(i); i = fa[i]) q[++top] = fa[i];
- while (top) pushdown(q[top--]);
- while (!isroot(x)) {
- int y = fa[x],
- z = fa[y];
- if (!isroot(y)) if (c[y][1] == x ^ c[z][1] == y) rotate(x);
- else rotate(y);
- rotate(x);
- }
- }
- void access(int x) {
- for (int t = 0; x; t = x, x = fa[x]) splay(x),
- c[x][1] = t,
- updata(x);
- }
- void makeroot(int x) {
- access(x);
- splay(x);
- reve(x);
- }
- void link(int x, int y) {
- makeroot(x);
- fa[x] = y;
- }
- void cut(int x, int y) {
- makeroot(x);
- access(y);
- splay(y);
- if (c[y][0] == x) fa[x] = c[y][0] = 0;
- }
- int main() {
- freopen(FILE ".in", "r", stdin);
- freopen(FILE ".out", "w", stdout);
- n = read(),
- m = read();
- cnt = n;
- up(i, 1, n) sum[i] = v[i] = read();
- int ch,
- x,
- y;
- while (m--) {
- ch = read(),
- x = read(),
- y = read();
- if (ch == 0) {
- makeroot(x),
- access(y),
- splay(y);
- printf("%d\n", sum[y]);
- }
- if (ch == 1) {
- makeroot(x);
- access(y);
- splay(y);
- int t = y;
- while (c[t][0]) t = c[t][0];
- if (t != x) link(x, y);
- }
- if (ch == 2) cut(x, y);
- if (ch == 3) {
- makeroot(x);
- v[x] = y;
- updata(x);
- }
- }
- return 0;
- }
来源: