BZOJ3282 Tree < LCT >

Posted on Symbols count in article: 809 Reading time ≈ 3 mins.

Problem

Tree

Time Limit: 30Sec30 Sec
Memory Limit: 512MB512 MB

Description

给定NN个点以及每个点的权值，要你处理接下来的MM个操作。操作有44种。操作从00到33编号。点从11到NN编号。
00.后接两个整数 (x,y)(x, y)，代表询问从xx到yy的路径上的点的权值的xorxor和。保证xx到yy是联通的。
11.后接两个整数 (x,y)(x, y)，代表连接xx到yy，若x到y已经联通则无需连接。
22.后接两个整数 (x,y)(x, y)，代表删除边$ (x, y)$，不保证边 (x,y)(x, y) 存在。
33.后接两个整数 (x,y)(x, y)，代表将点xx上的权值变成yy。

Input

第11行两个整数，分别为NN和MM，代表点数和操作数。
第22行到第N+1N+1行，每行一个整数，整数在 [1,109][1, 10^9] 内，代表每个点的权值。
第N+2N+2行到第N+M+1N+M+1行，每行三个整数，分别代表操作类型和操作所需的量。

Output

对于每一个00号操作，你须输出xx到yy的路径上点权的xorxor和。

Sample Input

1
2
3
4
5
6
7
3 3 
1
2
3
1 1 2
0 1 2 
0 1 1

Sample Output

1
2
3
1

Hint

1≤N,M≤3×1051\le N,M\le 3\times 10^5

标签：LCT

Solution

LCTLCT板子题
人生中的第一道LCTLCT
用了没带保护指针的splaysplay，有几个细节挺坑

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <bits/stdc++.h>
#define MAX_N 300000
#define INF 0x7f7f7f7f
#define flag (!tar(cur->fa->fa)&&cur->fa->fa->s[sn]==cur->fa)
using namespace std;
struct SplayNode {
    SplayNode *s[2], *fa;	int val, sum;	bool rev;
    void updata() {sum = val^(s[0]?s[0]->sum:0)^(s[1]?s[1]->sum:0);}
    void downtag() {
        if (fa && (fa->s[0] == this || fa->s[1] == this)) fa->downtag();
        if (rev && s[0]) swap(s[0]->s[0], s[0]->s[1]), s[0]->rev ^= 1;
        if (rev && s[1]) swap(s[1]->s[0], s[1]->s[1]), s[1]->rev ^= 1;
        rev = false;
    }
} *tr[MAX_N+5];
struct LinkCutTree {
    SplayNode* newnode(int _val) {
        SplayNode* v = new SplayNode;
        v->s[0] = v->s[1] = v->fa = NULL;
        v->val = v->sum = _val, v->rev = 0;
        return v;
    }
    SplayNode* get_rt(SplayNode* v) {for (; v->fa; v = v->fa) ;	return v;}
    bool tar(SplayNode* v) {return (v&&v->fa==NULL)||(v&&v->fa->s[0]!=v&&v->fa->s[1]!=v);}
    LinkCutTree(int n) {for (int i=1,_val;i<=n;i++) scanf("%d", &_val), tr[i]=newnode(_val);}
    void rotate(SplayNode* v, bool sn) {
        SplayNode* f = v->fa;
        f->s[sn^1] = v->s[sn], v->fa = f->fa;
        if (f->s[sn^1]) f->s[sn^1]->fa = f;
        if (v->fa && !tar(f)) v->fa->s[f == f->fa->s[1]] = v;
        v->s[sn] = f, f->fa = v, f->updata(), v->updata();
    }
    void splay(SplayNode* cur) {
        cur->downtag();
        while (!tar(cur) && !tar(cur->fa)) {
            bool sn = cur->fa->s[1] == cur;
            if flag rotate(cur->fa, sn^1);
            rotate(cur, sn^1);
        }
        if (!tar(cur) && tar(cur->fa))
            rotate(cur, cur->fa->s[0] == cur);
        cur->updata();
    }
    void access(SplayNode* cur) {
        for (SplayNode* cpy = NULL; cur; cpy = cur, cur = cur->fa)
            splay(cur), cur->s[1] = cpy, cur->updata();
    }
    void mroot(SplayNode* v) {
        access(v), splay(v);
        swap(v->s[0], v->s[1]), v->rev ^= 1;
    }
    void link(SplayNode* u, SplayNode* v) {
        if (get_rt(u) == get_rt(v)) return;
        mroot(u), u->fa = v;
    }
    void cut(SplayNode* u, SplayNode* v) {
        if (u == v || get_rt(u) != get_rt(v)) return;
        mroot(u), access(v), splay(v);
        if (v->s[0] == u) u->fa = v->s[0] = NULL, v->updata();
    }
    void modify(SplayNode* v, int _val) {
        splay(v), v->val = _val, v->updata();
    }
    int query(SplayNode* u, SplayNode* v) {
        mroot(u), access(v), splay(v);
        return v->sum;
    }
};
int main() {
    int n, m;	scanf("%d%d", &n, &m);
    LinkCutTree LCT(n);
    while (m--) {
        int opt, x, y;	scanf("%d%d%d", &opt, &x, &y);
        if (opt == 0) printf("%d\n", LCT.query(tr[x], tr[y]));
        if (opt == 1) LCT.link(tr[x], tr[y]);
        if (opt == 2) LCT.cut(tr[x], tr[y]);
        if (opt == 3) LCT.modify(tr[x], y);
    }
    return 0;
}