[Ynoi2017] 由乃的 OJ 水题LCT

题目思路

首先，原题是个傻逼题，所以这题也不会难

我们考虑每个点单独作为序列时的答案$ans0,ans1$，那么序列上树后我们需要考虑区间合并：假设带合并的两个答案分别为$a,b$，那么合并就是：

$a.ans0$ 的 第 $k$ 位为 $0$，并且 $b.ans0$ 的第 $k$ 位为 $1$ 或者 $a.ans0$ 的第 $k$ 位为 $1$ 而且 $b.ans1$ 的第 $k$ 位为 $1$，此时合并后 $ans0$ 第 $k$ 位仍为$1$。类似的可以推出$ans1$的合并条件。

然后考虑序列上树，需要树剖来算答案。然后可以用LCT维护这个东西，但是发现$makeRoot$操作会反转子树，因此需要额外维护每个区间的正反合并序答案，并在交换儿子的时候交换答案。

那么又是一个可以快速A掉的题。

另外，要吸氧

Code

#include 
#define int unsigned long long
#define ull unsigned long long
#define endl '\n'
using namespace std;

const int N = 1e6 + 10;

namespace LCT{
    #define ls ch[x][0]
    #define rs ch[x][1]

    struct Info {
        ull ans0, ans1;
        void assign(int op, int x) {
            if(op == 1) ans0 = 0, ans1 = x;
            if(op == 2) ans0 = x, ans1 = ~0;
            if(op == 3) ans0 = x, ans1 = ~x;
        }
        friend Info operator+ (Info a, Info b) {
            return Info {
                (~a.ans0 & b.ans0) | (a.ans0 & b.ans1),
                (~a.ans1 & b.ans0) | (a.ans1 & b.ans1) };
        }
    } ans[N], fnt[N], bak[N];
    
    int ch[N][2], f[N], val[N], tag[N], lazy[N], siz[N];


    inline void push_up(int x) {
        fnt[x] = bak[x] = ans[x];
        if(ls) fnt[x] = fnt[ls] + fnt[x], bak[x] = bak[x] + bak[ls];
        if(rs) fnt[x] = fnt[x] + fnt[rs], bak[x] = bak[rs] + bak[x];
    }

    inline void push(int x) { swap(ls, rs), swap(fnt[x], bak[x]), tag[x] ^= 1; }

    inline void push_down(int x) {
        if(tag[x]) {
            if(ls) push(ls);
            if(rs) push(rs);
            tag[x] = 0;
        }
    }

#define get(x) (ch[f[x]][1] == x)                        // 查询节点X是父亲的哪个儿子
    #define isRoot(x) (ch[f[x]][0] != x && ch[f[x]][1] != x) // 判断X是否是所在树的根

    inline void rotate(int x) { // 将X向上旋转一层
        int y = f[x], z = f[y], k = get(x);
        if(!isRoot(y)) ch[z][ch[z][1] == y] = x;
        ch[y][k] = ch[x][!k], f[ch[x][!k]] = y;
        ch[x][!k] = y, f[y] = x, f[x] = z;
        push_up(y); push_up(x);
    }

    inline void update(int x) { // X所在路径自上向下释放Lazy标记
        if(!isRoot(x)) update(f[x]);
        push_down(x);
    }

    inline void splay(int x) { // 将节点X旋至当前所在平衡树的树根(带LCT性质认子不认父)
        update(x);
        for(int fa = f[x]; !isRoot(x); rotate(x), fa = f[x]){
            if(!isRoot(fa)) rotate(get(fa) == get(x) ? fa : x);
        }
        push_up(x);
    }

    int access(int x) { // 把从根到X的所有点放在一条实链里，使根到X成为一条实路径
        int p;
        for(p = 0; x; x = f[p = x]) splay(x), ch[x][1] = p, push_up(x);
        return p;
    }

    void makeRoot(int p) { access(p), splay(p), push(p); } // 使X点成为其所在树的根

    int findRoot(int x) { // 找到X所在树的根节点编号
        access(x), splay(x);
        while(ch[x][0]) push_down(x), x = ch[x][0];
        splay(x);
        return x;
    }

    void link(int x, int y) { // 在x,y之间连边
        makeRoot(x);  f[x] = y;
    }
    
    void split(int x, int y) { // 提取出x,y之间的路径
        makeRoot(x);
        access(y), splay(y);
    }
}

int n, m, k;

int get_ans(int val0, int val1, int z) {
    int ans = 0;
    for(long long i = 63; i >= 0; --i) {
        if(val0 >> i & 1ull) ans += 1ull << i;
        else if(val1 >> i & 1ull && (1ull << i) <= z) ans += 1ull << i, z -= 1ull << i;
    }
    return ans;
}

inline void solve() {
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++) {
        ull x, op; cin >> op >> x;
        LCT::ans[i].assign(op, x);
    }
    for(int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        LCT::link(u, v);
    }   
    for(int i = 1; i <= m; i++) {
        ull op, x, y, z; cin >> op >> x >> y >> z;
        if(op == 1) {
            LCT::split(x, y);
            // cout << "#dng : " << LCT::fnt[y].ans0 << " " << LCT::fnt[y].ans1 << endl;
            cout << get_ans(LCT::fnt[y].ans0, LCT::fnt[y].ans1, z) << endl;
        } else {
            LCT::ans[x].assign(y, z);
            LCT::splay(x);
        }

    }
}

signed main() {
    ios_base::sync_with_stdio(false), cin.tie(0);
    int t = 1; // cin >> t;
    while(t--) solve();
    return 0;
}

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136