老师老师，我们家おゆぽ也太帅了吧🥰

准备在分治的路上一条道走到黑了。下一步是树分治和点分树。

概述

线段树分治是一种能够维护动态修改和查询操作的离线算法。修改操作包括添加和删除，一般来讲，查询和添加相对好做，而删除操作会比较困难。线段树分治顾名思义，通过把各个操作离线挂在线段树的各个节点上，进入一个节点就应用其上挂载的所有操作，离开节点前依赖可撤销结构恢复进入该节点之前的状态，进而巧妙的维护了删除操作。

从深搜线段树的角度来看，我们把操作按照顺序依次入栈，离开前反向依次弹出栈即可恢复原状，这就比在线算法显式维护修改操作方便了太多。

线段树分治最常见的应用是维护动态图的连通性，每条边在时间序列上有存在时间，按照存在的时间区间依次把边挂在到线段树的各个节点上就可以维护了。除了图的连通性，线段树分治当然也可以维护其他动态修改的数据。在后面的例题中，我们可以看到，线段树分治能够处理动态背包问题、动态线性基、动态维护Trie等等，非常灵活。

线段树分治常以时间序列建线段树，但也可以根据题目性质建别的线段树，例如答案值线段树、颜色线段树等等，需要见招拆招。

以维护动态图分析一下线段树分治的复杂度：设总时间为 $q$ ，一条边存在的时间段在时间线段树上分为 $O(\log{q})$ 个区间，共有 $m$ 条边，以可撤销并查集维护，单次查找父亲和合并的复杂度均为 $O(\log{n})$，因此时间总复杂度为 $O(m\log{q}\log{n})$，又是一个2log算法，这下看懂了（不是

例题

LOJ121 动态图连通性

动态加边删边，查询两点的连通性。

线段树分治模板题，建立时间线段树，把每条边的存在时段分成 $\log{n}$ 个区间挂在线段树节点上，借助可撤销并查集维护边，到叶子节点时若这个点对应查询操作记录答案。退出节点时撤销并查集的修改。

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
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 0
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

constexpr int N = 5e3 + 10;
constexpr int M = 5e5 + 10;
constexpr int MOD = 998244353;


#define lc u<<1
#define rc u<<1|1
int mp[N][N];
int op[M], x[M], y[M];
int ans[M];
int fa[N], sz[N], top;
tuple<int, int> stk[M];
vector<tuple<int, int>> e[M << 2];

int find(int x) {
    while (x != fa[x]) {
        x = fa[x];
    }
    return x;
}

void merge(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return;
    if (sz[x] < sz[y]) swap(x, y);
    fa[y] = x;
    sz[x] += sz[y];
    stk[++top] = {x, y};
}

void undo() {
    auto [x, y] = stk[top--];
    fa[y] = y;
    sz[x] -= sz[y];
}

void modify(int u, int l, int r, int ql, int qr, int x, int y) {
    if (ql <= l && qr >= r) {
        e[u].push_back({x, y});
        return;
    }
    int mid = l + r >> 1;
    if (mid >= ql) modify(lc, l, mid, ql, qr, x, y);
    if (mid < qr)  modify(rc, mid + 1, r, ql, qr, x, y);
}

void kasta(int u, int l, int r) {
    int cnt = 0;
    for (auto [x, y] : e[u]) {
        x = find(x), y = find(y);
        if (x == y) continue;
        merge(x, y);
        cnt++;
    }
    if (l == r) {
        if (op[l] == 2) ans[l] = find(x[l]) == find(y[l]);
    } else {
        int mid = l + r >> 1;
        kasta(lc, l, mid);
        kasta(rc, mid + 1, r);
    }
    while (cnt--) {
        undo();
    }
}

void solve() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        cin >> op[i] >> x[i] >> y[i];
        if (x[i] > y[i]) swap(x[i], y[i]);
        if (op[i] == 0) mp[x[i]][y[i]] = i;
        else if (op[i] == 1) {
            modify(1, 1, m, mp[x[i]][y[i]], i - 1, x[i], y[i]);
            mp[x[i]][y[i]] = 0;
        }
    }
    for (int x = 1; x <= n; ++x) {
        for (int y = x + 1; y <= n; ++y) {
            if (mp[x][y]) modify(1, 1, m, mp[x][y], m, x, y);
        }
    }
    for (int i = 1; i <= n; ++i) fa[i] = i, sz[i] = 1;
    kasta(1, 1, m);
    for (int i = 1; i <= m; ++i) {
        if (op[i] == 2) {
            cout << (ans[i] ? "Y\n" : "N\n");
        }
    }
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

P5787 二分图 /【模板】线段树分治

动态加边删边，判断每个时刻图是否是二分图。

和连通性类似的处理，判断二分图借助可撤销扩展域并查集。

一个剪枝：一旦变成非二分图，后续加边也一直是非二分图，无需再向深处遍历。

P5631 最小mex生成树

给定带边权连通无向图，求边权集合mex最小的生成树的mex值。

建立答案线段树，设边权最大值为w，认为边权为v的边生效区间是 $[0,v-1]\cup[v+1,w]$，直接深搜线段数，到每个叶子结点时判断当前图是否连通，若连通则当前节点对应的值就是答案，后续直接返回即可。

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
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 0
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

constexpr int N = 1e6 + 10;
constexpr int W = 1e5 + 10;
constexpr int MOD = 998244353;

#define lc u<<1
#define rc u<<1|1
vector<tuple<int, int>> e[W << 2];
int fa[N], sz[N], top, part, ans = -1;
tuple<int, int> stk[N << 1];

int find(int x) {
    while (x != fa[x]) x = fa[x];
    return x;
}

void merge(int x, int y) {
    x = find(x), y = find(y);
    if (sz[x] < sz[y]) swap(x, y);
    fa[y] = x;
    sz[x] += sz[y];
    stk[++top] = {x, y};
}

void undo() {
    auto [x, y] = stk[top--];
    fa[y] = y;;
    sz[x] -= sz[y];
}

void modify(int u, int l, int r, int ql, int qr, int x, int y) {
    if (ql <= l && qr >= r) {
        e[u].emplace_back(x, y);
        return;
    }
    int mid = l + r >> 1;
    if (ql <= mid) modify(lc, l, mid, ql, qr, x, y);
    if (qr > mid)  modify(rc, mid + 1, r, ql, qr, x, y);
}

void dfs(int u, int l, int r) {
    int cnt = 0;
    for (auto [x, y] : e[u]) {
        x = find(x), y = find(y);
        if (x == y) continue;
        merge(x, y);
        cnt++;
        part--;
    }
    if (l == r) {
        if (part == 1) ans = l;
    } else {
        int mid = l + r >> 1;
        dfs(lc, l, mid);
        if (ans == -1) dfs(rc, mid + 1, r);
    }
    while (cnt--) {
        undo();
        part++;
    }
}

void solve() {
    int n, m;
    cin >> n >> m;
    part = n;
    for (int i = 1; i <= n; ++i) fa[i] = i, sz[i] = 1;
    for (int i = 0, u, v, w; i < m; ++i) {
        cin >> u >> v >> w;
        if (w) modify(1, 0, W, 0, w - 1, u, v);
        modify(1, 0, W, w + 1, W, u, v);
    }
    dfs(1, 0, W);
    cout << ans << "\n";
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

CF1681F Unique Occurrences

给定 $n$ 个点的带边权树，设 $f(u,v)$ 为 $u$ 到 $v$ 简单路径上恰好出现一次的权值个数，求 $\sum\limits_{u=1}^{n}\sum\limits_{v=u+1}^{n}f(u,v) $。

建立颜色线段树，每种颜色的边的生效区间是 $[1,c-1]\cup[c+1,w]$ ，每次遍历到叶子节点时，显然会有若干联通块，任意取两个块，各取一个点，叶子结点对应的边权都会在这两个点之间的路径上只出现一次，因此分步计算所有颜色对答案的贡献，累加即可。

P4219 [BJOI2014] 大融合

加边动态图，查询某条边两端节点所在联通块大小的乘积。

查询时认为该边不存在，离线所有操作，处理每条边的存在时间，挂在时间线段树上，依次进行处理。

P5227 [AHOI2013] 连通图

给定连通无向图和若干边集合，查询删掉某个边集合的所有边后图是否连通。

跟前几道题做法类似，处理好每条边的存在时间区间，挂在时间线段树上进行处理。

CF576E Painting Edges

给定连通无向图，初始每条边均无色，动态给某条边染色，若操作后保留任何一种颜色的子图都是二分图则合法，否则非法且撤销操作。判断每次操作是否合法。

颜色种类很少，对每一种颜色独立建立可撤销扩展域并查集。依旧维护每条边的存在时间，染色视为删边再加边。到叶子结点后若发现染色失败，把此次要染的颜色换回原色。

细节比较多，慢慢调。

利用了线段树分治的半在线性。

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
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 0
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

constexpr int N = 5e5 + 10;
constexpr int K = 51;
constexpr int MOD = 998244353;

#define lc u<<1
#define rc u<<1|1
vector<int> E[N << 2];
int fa[K][N << 1], sz[K][N << 1], top;
int x[N], y[N], e[N], c[N];
tuple<int, int, int> stk[N << 1];
int lastColor[N], post[N], ans[N];
int n, m, k, q;

int find(int c, int x) {
    while (x != fa[c][x]) x = fa[c][x];
    return x;
}

void merge(int c, int x, int y) {
    x = find(c, x), y = find(c, y);
    if (sz[c][x] < sz[c][y]) swap(x, y);
    fa[c][y] = x;
    sz[c][x] += sz[c][y];
    stk[++top] = {c, x, y};
}

void undo() {
    auto [c, x, y] = stk[top--];
    fa[c][y] = y;
    sz[c][x] -= sz[c][y];
}

void modify(int u, int l, int r, int ql, int qr, int i) {
    if (ql <= l && qr >= r) {
        E[u].push_back(i);
        return;
    }
    int mid = l + r >> 1;
    if (ql <= mid) modify(lc, l, mid, ql, qr, i);
    if (qr > mid)  modify(rc, mid + 1, r, ql, qr, i);
}

void dfs(int u, int l, int r) {
    int cnt = 0;
    for (auto i : E[u]) {
        int _e = e[i];
        int _c = c[i];
        int _x = x[_e], _y = y[_e];
        int x1 = _x + n, y1 = _y + n;
        _x = find(_c, _x), _y = find(_c, _y), x1 = find(_c, x1), y1 = find(_c, y1);
        if (_x != y1) {
            merge(_c, _x, y1);
            cnt++;
        }
        if (_y != x1) {
            merge(_c, _y, x1);
            cnt++;
        }
    }
    if (l == r) {
        if (find(c[l], x[e[l]]) == find(c[l], y[e[l]])) {
            c[l] = lastColor[e[l]];
        } else {
            ans[l] = 1;
            lastColor[e[l]] = c[l];
        }
    } else {
        int mid = l + r >> 1;
        dfs(lc, l, mid);
        dfs(rc, mid + 1, r);
    }
    while (cnt--) {
        undo();
    }
}

void solve() {
    
    cin >> n >> m >> k >> q;
    for (int i = 1; i <= m; ++i) {
        cin >> x[i] >> y[i];
    }
    for (int i = 1; i <= q; ++i) {
        cin >> e[i] >> c[i];
    }
    for (int c = 1; c <= k; ++c) {
        for (int i = 1; i <= 2 * n; ++i) {
            fa[c][i] = i;
            sz[c][i] = 1;
        }
    }
    for (int i = 1; i <= q; ++i) {
        post[e[i]] = q;
    }
    for (int i = q; i >= 1; --i) {
        if (i + 1 > post[e[i]]) continue;
        modify(1, 1, q, i + 1, post[e[i]], i);
        post[e[i]] = i;
    }
    dfs(1, 1, q);
    for (int i = 1; i <= q; ++i) cout << (ans[i] ? "YES" : "NO") << "\n";
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

CF601E A Museum Robbery

物品有价值和重量，动态增删物品集合，查询从 $1$ 到 $k$ 每种最大重量下选取物品集合所能获得的物品最大价值。

线段树分治动态维护01背包。和维护图连通性很类似，处理每种物品的存在时间，挂载到时间线段树的对应节点上，每次进入节点时备份dp数组，新拿到物品更新dp数组，退出节点时恢复进入前的dp数组的状态即可。

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
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 0
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

template<typename T> void chkmin(T& a, T b) { a = min(a, b); }
template<typename T> void chkmax(T& a, T b) { a = max(a, b); }

constexpr int N = 1e3 + 10;
constexpr int Q = 3e4 + 10;
constexpr int LOG = 20;
constexpr int BAS = 1e7 + 19;
constexpr int MOD = 1e9 + 7;

#define lc u<<1
#define rc u<<1|1
i64 dp[N], bak[LOG][N];
vector<int> e[Q << 2];
int v[Q << 1], w[Q << 1];
int st[Q << 1], ed[Q << 1], op[Q];
i64 ans[Q];
int n, k, q;

void modify(int u, int l, int r, int ql, int qr, int i) {
    if (ql <= l && qr >= r) {
        e[u].push_back(i);
        return;
    }
    int mid = l + r >> 1;
    if (ql <= mid) modify(lc, l, mid, ql, qr, i);
    if (qr > mid)  modify(rc, mid + 1, r, ql, qr, i);
}

void dfs(int u, int l, int r) {
    int d = __lg(u);
    for (int i = 0; i <= k; ++i) bak[d][i] = dp[i];
    for (int i : e[u]) {
        for (int j = k; j >= w[i]; --j) {
            chkmax(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    if (l == r) {
        if (op[l] == 3) {
            i64 res = 0;
            i64 x = 1;
            for (int i = 1; i <= k; ++i) {
                res = (res + dp[i] * x) % MOD;
                x = (x * BAS) % MOD;
            }
            ans[l] = res;
        } 
    } else {
        int mid = l + r >> 1;
        dfs(lc, l, mid);
        dfs(rc, mid + 1, r);
    }
    for (int i = 0; i <= k; ++i) dp[i] = bak[d][i];
}

void solve() {
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        cin >> v[i] >> w[i];
    }
    cin >> q;
    for (int i = 1; i <= n; ++i) {
        st[i] = 1;
        ed[i] = q;
    }
    for (int i = 1; i <= q; ++i) {
        int x, y;
        cin >> op[i];
        if (op[i] == 1) {
            cin >> x >> y;
            ++n;
            v[n] = x, w[n] = y;
            st[n] = i;
            ed[n] = q;
        } else if (op[i] == 2) {
            cin >> x;
            ed[x] = i - 1;
        } 
    }
    for (int i = 1; i <= n; ++i) {
        if (st[i] > ed[i]) continue;
        modify(1, 1, q, st[i], ed[i], i);
    }
    dfs(1, 1, q);
    for (int i = 1; i <= q; ++i) if (op[i] == 3) cout << ans[i] << "\n";
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

LOJ6515 「雅礼集训 2018 Day10」贪玩蓝月

初始一个空的双端队列，动态向两端增删物品，查询队列中所有物品重量之和模意义下在某个范围内所能获得的最大价值。

跟双端队列关系不大，只关心物品的存在时间区间即可，做法和上一题类似。注意dp数组里非法状态置-1。

CF981E Addition on Segments

给定初始为空的序列，可选若干次给定范围和值的区间加，询问任意选取若干条操作后1~n中多少种值可以成为序列的最大值。

建立位置线段树，把所有区间加操作离线到线段树上，类似01背包的方式做转移。值域比较小，可以使用bitset加速。最后取所有叶子结点的并集即可。

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
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 0
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

constexpr int N = 1e4 + 10;
constexpr int MOD = 998244353;

#define lc u<<1
#define rc u<<1|1
bitset<10001> dp, ans, tmp[20];
vector<int> e[N << 2];
int n, q;

void modify(int u, int l, int r, int ql, int qr, int x) {
    if (ql <= l && qr >= r) {
        e[u].push_back(x);
        return;
    }   
    int mid = l + r >> 1;
    if (ql <= mid) modify(lc, l, mid, ql, qr, x);
    if (qr > mid)  modify(rc, mid + 1, r, ql, qr, x);
}

void dfs(int u, int l, int r) {
    tmp[__lg(u)] = dp;
    for (int x : e[u]) {
        dp |= (dp << x);
    }
    if (l == r) {
        ans |= dp;
    } else {
        int mid = l + r >> 1;
        dfs(lc, l, mid);
        dfs(rc, mid + 1, r);
    }
    dp = tmp[__lg(u)];
}

void solve() {
    cin >> n >> q;
    for (int i = 1; i <= q; ++i) {
        int l, r, x;
        cin >> l >> r >> x;
        modify(1, 1, n, l, r, x);
    }
    dp[0] = 1;
    dfs(1, 1, n);
    int cnt = 0;
    for (int i = ans._Find_next(0); i != ans.size() && i <= n; i = ans._Find_next(i)) {
        cnt++;
    }
    cout << cnt << "\n";
    for (int i = ans._Find_next(0); i != ans.size() && i <= n; i = ans._Find_next(i)) {
        cout << i << " ";
    }
    cout << "\n";
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

CF938G Shortest Path Queries

无向带权图动态加边删边，保证图始终联通，无重边，无自环，询问两点之间任意路径最小异或和。

普通加边删边通过线段树分治显然，但如何处理询问？需要使用线性基搭配可撤销带权并查集。

前置题目：P4151 [WC2011] 最大XOR和路径

我们维护图上所有环的异或和组成的线性基，询问操作分为两步，第一步获得两点之间任意一条路径的异或和，第二步使用线性基计算最小值。第一步通过带权并查集可维护，需要注意的是这里是可撤销并查集，因此还是不路径压缩，只做启发式合并。线性基计算最小值基于贪心思想从高位扫到低位即可。

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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 0
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

template<typename T> void chkmin(T& a, T b) { a = min(a, b); }
template<typename T> void chkmax(T& a, T b) { a = max(a, b); }

constexpr int N = 2e5 + 10;
constexpr int BIT = 30;
constexpr int MOD = 998244353;

#define lc u<<1
#define rc u<<1|1
vector<tuple<int, int, int>> e[N << 2];
int op[N], x[N], y[N], w[N], ans[N];
array<int, 4> a[N << 1];
int fa[N], sz[N], eor[N], top;
tuple<int, int> stk[N << 1];
int basis[BIT], pos[BIT], basiz;
int n, m, q;

void insert(int x) {
    for (int i = BIT - 1; i >= 0; --i) {
        if (x >> i & 1) {
            if (basis[i] == 0) {
                basis[i] = x;
                pos[++basiz] = i;
                return;
            }
            x ^= basis[i];
        }
    }
}

int minXor(int x) {
    for (int i = BIT - 1; i >= 0; --i) chkmin(x, x ^ basis[i]);
    return x;
}

void cancel(int cnt) {
    while (cnt < basiz) {
        basis[pos[basiz--]] = 0;
    }
}

int find(int x) {
    while (x != fa[x]) x = fa[x];
    return x;
}

int getXor(int x) {
    int res = 0;
    while (x != fa[x]) {
        res ^= eor[x];
        x = fa[x];
    }
    return res;
}

bool merge(int x, int y, int w) {
    w ^= getXor(x) ^ getXor(y);
    x = find(x), y = find(y);
    if (x == y) {
        insert(w);
        return false;
    }
    if (sz[x] < sz[y]) swap(x, y);
    fa[y] = x;
    sz[x] += sz[y];
    eor[y] = w;
    stk[++top] = {x, y};
    return true;
}

void undo() {
    auto [x, y] = stk[top--];
    fa[y] = y;
    sz[x] -= sz[y];
    eor[y] = 0; 
}

void modify(int u, int l, int r, int ql, int qr, int x, int y, int w) {
    if (ql <= l && qr >= r) {
        e[u].emplace_back(x, y, w);
        return;
    }
    int mid = l + r >> 1;
    if (ql <= mid) modify(lc, l, mid, ql, qr, x, y, w);
    if (qr > mid)  modify(rc, mid + 1, r, ql, qr, x, y, w);
}

void dfs(int u, int l, int r) {
    int oldsiz = basiz;
    int cnt = 0;
    for (auto [x, y, w] : e[u]) {
        if (merge(x, y, w)) {
            cnt++;
        }
    }
    if (l == r) {
        if (op[l] == 3) {
            ans[l] = minXor(getXor(x[l]) ^ getXor(y[l]));
        }
    } else {
        int mid = l + r >> 1;
        dfs(lc, l, mid);
        dfs(rc, mid + 1, r);
    }
    cancel(oldsiz);
    while (cnt--) {
        undo();
    }
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        auto& [x, y, t, w] = a[i];
        cin >> x >> y >> w;
        t = 0;
    }
    cin >> q;
    for (int i = 1; i <= q; ++i) {
        cin >> op[i] >> x[i] >> y[i];
        if (op[i] == 1) cin >> w[i];
        if (op[i] != 3) {
            auto& [x1, y1, t, w1] = a[++m];
            x1 = x[i];
            y1 = y[i];
            t = i;
            w1 = w[i];
        }
    }
    for (int i = 1; i <= n; ++i) fa[i] = i, sz[i] = 1;
    sort(a + 1, a + m + 1, [&](auto x, auto y) {
        if (x[0] != y[0]) return x[0] < y[0];
        if (x[1] != y[1]) return x[1] < y[1];
        return x[2] < y[2];
    });
    for (int l = 1, r = 1; l <= m; l = ++r) {
        int u = a[l][0], v = a[l][1];
        while (r + 1 <= m && a[r + 1][0] == u && a[r + 1][1] == v) r++;
        for (int i = l; i <= r; i += 2) {
            int d = a[i][3];
            int st = a[i][2], ed = (i + 1 <= r ? a[i + 1][2] - 1 : q);
            modify(1, 0, q, st, ed, u, v, d);
        }
    }
    dfs(1, 0, q);
    for (int i = 1; i <= q; ++i) {
        if (op[i] == 3) cout << ans[i] << "\n";
    }
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

P3733 [HAOI2017] 八纵八横

初始给定带边权连通图，动态加边删边改边权，保证图始终联通，路径可以重复经过，询问每个时间节点从1号点出发回到1号点的最大路径权值异或和。

跟上一道题很像，好处在于始终联通，因此不需要使用可撤销并查集，使用经典带权并查集即可维护，线段树分治的时候只撤销线性基。

怎么求1号点所在环的最大路径异或和？根据定义，1号点到自己本身也算一个环，因此还是按照最大XOR和路径那道题的做法，初始获得一个异或和为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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 0
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;
using bs = bitset<1000>;

constexpr int N = 1e3 + 10;
constexpr int BIT = 1000;
constexpr int MOD = 998244353;

#define lc u<<1
#define rc u<<1|1
int op[N], x[N], y[N];
vector<tuple<int, int, bs>> e[N << 2];
bs ans[N], w[N], basis[BIT], eor[N];
int basiz, pos[BIT];
int fa[N];
int last[N];
int n, m, q;

void insert(bs& w) {
    for (int i = BIT - 1; i >= 0; --i) {
        if (w[i]) {
            if (basis[i][i] == 0) {
                basis[i] = w;
                pos[++basiz] = i;
                return;
            }
            w ^= basis[i];
        }
    }
}

void cancel(int oldsiz) {
    while (basiz > oldsiz) {
        basis[pos[basiz--]].reset();
    }
}

bs getMax() {
    bs res;
    for (int i = BIT - 1; i >= 0; --i) {
        if (res[i] == 0 && basis[i][i] == 1) {
            res ^= basis[i];
        }
    }
    return res;
}

int find(int x) {
    if (x != fa[x]) {
        int t = fa[x];
        fa[x] = find(t);
        eor[x] ^= eor[t];
    }
    return fa[x];
}

bs getXor(int x) {
    find(x);
    return eor[x];
}

void merge(int x, int y, bs& w) {
    bs ww = w ^ getXor(x) ^ getXor(y);
    x = find(x), y = find(y);
    if (x == y) {
        insert(ww);
    } else {
        fa[y] = x;
        eor[y] = ww;
    }
}

void modify(int u, int l, int r, int ql, int qr, int x, int y, bs& w) {
    if (ql <= l && qr >= r) {
        e[u].emplace_back(x, y, w);
        return;
    }
    int mid = l + r >> 1;
    if (ql <= mid) modify(lc, l, mid, ql, qr, x, y, w);
    if (qr > mid)  modify(rc, mid + 1, r, ql, qr, x, y, w);
}   

void dfs(int u, int l, int r) {
    int oldsiz = basiz;
    for (auto [x, y, w] : e[u]) {
        merge(x, y, w);
    }
    if (l == r) {
        ans[l] = getMax();
    } else {
        int mid = l + r >> 1;
        dfs(lc, l, mid);
        dfs(rc, mid + 1, r);
    }
    cancel(oldsiz);
}

void print(bs& w) {
    bool ok = 0;
    for (int i = BIT - 1; i >= 0; --i) {
        if (w[i]) ok = 1;
        if (ok) {
            cout << w[i];
        }
    }
    if (!ok) cout << 0;
    cout << "\n";
}

void solve() {
    cin >> n >> m >> q;
    for (int i = 0; i < BIT; ++i) basis[i].reset();
    for (int i = 1; i <= n; ++i) eor[i].reset();
    for (int i = 1; i <= n; ++i) fa[i] = i;
    for (int i = 1; i <= m; ++i) {
        int x, y;
        bs w;
        cin >> x >> y >> w;
        merge(x, y, w);
    }
    ans[0] = getMax();
    m = 0;
    for (int i = 1; i <= q; ++i) {
        string s;
        cin >> s;
        if (s[0] == 'A') {
            m++;
            cin >> x[m] >> y[m] >> w[m];
            last[m] = i;
        } else if (s[1] == 'a') {
            int k;
            cin >> k;
            modify(1, 1, q, last[k], i - 1, x[k], y[k], w[k]);
            last[k] = 0;
        } else {
            int k;
            cin >> k;
            modify(1, 1, q, last[k], i - 1, x[k], y[k], w[k]);
            cin >> w[k];
            last[k] = i;
        }
    }
    for (int i = 1; i <= m; ++i) {
        if (last[i]) modify(1, 1, q, last[i], q, x[i], y[i], w[i]);
    }
    if (q) {
        dfs(1, 1, q);
    }
    for (int i = 0; i <= q; ++i) {
        print(ans[i]);
    }
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}
// 2025-8-21 11:14:09
// 2025-8-21 11:47:58

P4585 [FJOI2015] 火星商店问题

n个商店，初始每个商店有一种带权值的商品，动态给某家商店添加商品，查询在一个区间内的商店初始和某天前一段时间内新增的商品中，与给定值异或和的最大值。

先不考虑新增，静态版本就是可持久化01Trie板子题，基于贪心从高到低开始做。

新增的商品如何处理？考虑线段树分治，建立时间轴线段树，添加商品则单点加，给途经线段树节点都加上这个商品；询问则和普遍做法一样，拆成 $\log{n}$ 个区间挂在线段树的节点上。先以初始情况建持久化01Trie拿到备选答案值，搜到某个节点时，把这个节点上含有的所有商品按照商店编号排序，建立这个节点对应的新可持久化01Trie（之前建的Trie可直接覆盖，因为之后再也不会用到），每次得到的答案值取最大值即可。

看似很暴力，但是仔细分析时间复杂度，还是 $O(n\log^{2}{n})$ 的级别，完全可以通过。

实测vector和前向星存询问和修改的时间差距不大，前向星略好一点点，但差距几乎可以忽略不计，还是vector好写啊（

记得可持久化01Trie的空间一定要多开一点！因为Trie要额外保存顶部空节点，会多占用一些位置！

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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 0
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

template<typename T> void chkmin(T& a, T b) { a = min(a, b); }
template<typename T> void chkmax(T& a, T b) { a = max(a, b); }

constexpr int N = 1e5 + 10;
constexpr int M = 2e6 + 10;
constexpr int BIT = 16;
constexpr int MOD = 998244353;

#define lc u<<1
#define rc u<<1|1
int n, m;
int arr[N];
int ans[N];
int op[N], qs[N], qv[N], ql[N], qr[N], qx[N], qd[N], tim[N];

// 空间一定要开够！多开点没问题
int root[N], ch[M][2], cnt[M], cntt; 

vector<int> P[N << 2];
vector<int> B[N << 2];

// int headp[N << 2], nextp[M], pid[M], cntp;
// int headb[N << 2], nextb[M], bid[M], cntb;

array<int, 2> product[N];

// void addInfoP(int i, int pi) {
//     nextp[++cntp] = headp[i];
//     pid[cntp] = pi;
//     headp[i] = cntp;
// }

// void addInfoB(int i, int bi) {
//     nextb[++cntb] = headb[i];
//     bid[cntb] = bi;
//     headb[i] = cntb;
// }

// 基于x版本生成新版本的可持久化01trie
int insert(int v, int x) {
    int rt = ++cntt;
    ch[rt][0] = ch[x][0];
    ch[rt][1] = ch[x][1];
    cnt[rt] = cnt[x] + 1;
    for (int i = BIT, pre = rt, cur; i >= 0; --i, pre = cur) {
        int j = (v >> i) & 1;
        x = ch[x][j];
        cur = ++cntt;
        ch[cur][0] = ch[x][0];
        ch[cur][1] = ch[x][1];
        cnt[cur] = cnt[x] + 1;
        ch[pre][j] = cur;
    }
    return rt;
}

int query(int v, int x, int y) {
    int ans = 0;
    for (int i = BIT; i >= 0; --i) {
        int j = (v >> i) & 1;
        if (cnt[ch[y][!j]] > cnt[ch[x][!j]]) {
            ans += 1 << i;
            x = ch[x][!j];
            y = ch[y][!j];
        } else {
            x = ch[x][j];
            y = ch[y][j];
        }
    }
    return ans;
}

void addProduct(int u, int l, int r, int p, int i) {
    P[u].emplace_back(i);
    // addInfoP(u, i);
    if (l == r) return;
    int mid = l + r >> 1;
    if (p <= mid) addProduct(lc, l, mid, p, i);
    else addProduct(rc, mid + 1, r, p, i);
}

void addBuy(int u, int l, int r, int ql, int qr, int i) {
    if (ql <= l && qr >= r) {
        B[u].emplace_back(i);
        // addInfoB(u, i);
        return;
    }
    int mid = l + r >> 1;
    if (ql <= mid) addBuy(lc, l, mid, ql, qr, i);
    if (qr > mid)  addBuy(rc, mid + 1, r, ql, qr, i);
}

void dfs(int u, int l, int r) {
    int cnt = 0;
    for (int i : P[u]) {
    // for (int e = headp[u]; e; e = nextp[e]) {
        // int i = pid[e];
        product[++cnt] = {qs[i], qv[i]};
    }
    sort(product + 1, product + cnt + 1, [&](auto x, auto y) {
        return x[0] < y[0];
    });
    cntt = 0;
    for (int i = 1; i <= cnt; ++i) {
        root[i] = insert(product[i][1], root[i - 1]);
    }
    for (int i : B[u]) {
    // for (int e = headb[u]; e; e = nextb[e]) {
        // int i = bid[e];
        int l = lower_bound(product + 1, product + 1 + cnt, ql[i], [&](auto x, int v) { return x[0] < v; }) - product;
        int r = lower_bound(product + 1, product + 1 + cnt, qr[i] + 1, [&](auto x, int v) { return x[0] < v; }) - product - 1;
        chkmax(ans[i], query(qx[i], root[l - 1], root[r]));
    }
    if (l < r) {
        int mid = l + r >> 1;
        dfs(lc, l, mid);
        dfs(rc, mid + 1, r);
    }
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> arr[i];
    int t = 0;
    for (int i = 1; i <= m; ++i) {
        cin >> op[i];
        if (op[i] == 0) {
            t++;
            cin >> qs[i] >> qv[i];
        } else {
            cin >> ql[i] >> qr[i] >> qx[i] >> qd[i];
        }
        tim[i] = t;
    }
    for (int i = 1; i <= n; ++i) {
        root[i] = insert(arr[i], root[i - 1]);
    }
    for (int i = 1; i <= m; ++i) {
        if (op[i] == 0) {
            addProduct(1, 1, t, tim[i], i);
        } else {
            ans[i] = query(qx[i], root[ql[i] - 1], root[qr[i]]);
            int st = max(1, tim[i] - qd[i] + 1);
            if (st <= tim[i]) addBuy(1, 1, t, st, tim[i], i);
        }
    }
    dfs(1, 1, t);
    for (int i = 1; i <= m; ++i) if (op[i] == 1) cout << ans[i] << "\n";
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

结语

线段树分治为很多不便于删除的操作提供了一种离线的视角，用一个log的代价使其便于撤销。

当然要注意，不要所有涉及到动态增删的题目都线段树分治一把梭，先具体分析题目性质，很多时候贪心一下、转化一下也能做，学新算法是提供新视角，不是再次僵化视角。

例如 ABC308G Minimum Xor Pair Query，动态增删数集合，查询现有数集合中两个数的最小异或和。看着很像火星商店，线段树分治也显然能做，但是数据量太大，有T的风险。仔细分析题目，发现直接建普通Trie，借助贪心即可，比线段树分治做法少一个log。

不过不管怎么说，线段树分治总归还是一种很强力的工具，灵活使用必有奇效。🤗