「Ynoi2011」成都七中

发表于 分类于 本文字数： 2.5k 阅读时长 ≈ 9 分钟

Description

Link：Luogu P5311

给出一棵包含 nn 个点的树，每个节点有一种颜色 cic_i。

有 mm 次查询，每次查询给出三个参数 l,r,xl, r, x，表示询问只保留编号在 [l,r][l, r] 范围内的点时，xx 所在连通块的颜色种类数。

数据范围：1≤n,m≤1051 \leq n, m \leq 10^5，1≤ci≤n1 \leq c_i \leq n，1≤l≤x≤r≤n1 \leq l \leq x \leq r \leq n。

时空限制：11s / 250250MiB。

Solution

算法一：点分治

考虑与 xx 在同一个连通块的节点 yy，显然要满足从 xx 到 yy 的简单路径上经过的所有点中，编号最小值 ≥l\geq l，编号最大值 ≤r\leq r。

如果可以从 xx 只经过编号在 [l,r][l, r] 内的点到达 x′x'，则询问 l,r,xl, r, x 可以等价于询问 l,r,x′l, r, x'（相当于从 x′x' 出发）。

如果不能从 xx 只经过编号在 [l,r][l, r] 内的点到达 x′x'，则整棵树可以被 x′x' 划分成若干个连通块，由于 xx 不能到达 x′x'，故 xx 无法穿过 x′x' 到达其他的连通块。

这启发我们进行点分治，对于当前的分治中心 rt\mathrm{rt}，我们处理出 rt\mathrm{rt} 到达当前连通块每个点 ii 的简单路径上，编号最小值 lei\mathrm{le}_i 和编号最大值 rgi\mathrm{rg}_i。

对于一个询问 l,r,xl, r, x，若可以从 rt\mathrm{rt} 只经过编号在 [l,r][l, r] 内的点到达 xx（即 l≤leil \leq \mathrm{le}_i 且 rgi≤r\mathrm{rg}_i \leq r），则询问 l,r,xl, r, x 相当于询问 l,r,rtl, r, \mathrm{rt}；如果不能到达 xx，则当前连通块又被 rt\mathrm{rt} 划分成了若干个连通块，按照点分治的模式继续分治即可。

现在的目标就是要解决询问 l,r,rtl, r, \mathrm{rt}。对于当前连通块内的一个点 ii，若满足 l≤leil \leq \mathrm{le}_i 且 rgi≤r\mathrm{rg}_i \leq r，则就会对答案有一个 coli\mathrm{col}_i 颜色的贡献。发现这可以简单地扫描线解决，不过多赘述。

时间复杂度 O(nlog⁡2n+mlog⁡n)\mathcal{O}(n \log^2 n + m \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
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
183
184
185
186
187
188
189
190
#include <bits/stdc++.h>

#define debug(a) std::cout << #a << "=" << (a) << ' '

using s64 = long long;
using u64 = unsigned long long;

/* 取 min */
template <class T>
inline void chmin(T &x, const T &y) {
    if (x > y) {
        x = y;
    }
}
/* 取 max */
template <class T>
inline void chmax(T &x, const T &y) {
    if (x < y) {
        x = y;
    }
}

/* ----- ----- ----- 正文 ----- ----- ----- */

const int N = 100100;

int n, m;
int col[N];

struct Graph {
    std::vector< std::vector<int> > table;

    void init(int _n) {
        table.assign(_n + 1, {});
    }

    void add_edge(int u, int v) {
        table[u].push_back(v);
    }
} G;

int ban[N];

int sz[N], mp[N];
int tot_sz, tot_rt;

void GetRoot(int u, int fu) {
    sz[u] = 1, mp[u] = 0;
    for (int v : G.table[u]) {
        if (v == fu || ban[v]) continue;
        GetRoot(v, u);
        sz[u] += sz[v];
        chmax(mp[u], sz[v]);
    }
    chmax(mp[u], tot_sz - sz[u]);
    if (tot_rt == 0 || mp[u] < mp[tot_rt]) tot_rt = u;
}

std::vector<int> seq;
int le[N], rg[N];

void find(int u, int fu) {
    seq.push_back(u);

    le[u] = rg[u] = u;
    if (fu) chmin(le[u], le[fu]), chmax(rg[u], rg[fu]);

    for (int v : G.table[u]) {
        if (v == fu || ban[v]) continue;
        find(v, u);
    }
} 

std::vector< std::tuple<int, int, int> > qry[N];
int ans[N];

int lst[N];

namespace BIT {
    int c[N];

    void add(int x, int y) {
        for (; x <= n; x += x & -x) {
            c[x] += y;
        }
    }

    int ask(int x) {
        int ans = 0;
        for (; x; x -= x & -x) {
            ans += c[x];
        }
        return ans;
    }
}

void solve(int u) {
    ban[u] = 1;

    seq.clear();
    find(u, 0);

    std::vector< std::array<int, 3> > op;
    std::vector< std::array<int, 3> > qr;

    for (int x : seq) {
        op.push_back({rg[x], le[x], col[x]});
    }

    for (int x : seq) {
        for (auto &[l, r, id] : qry[x]) {
            if (id == -1) continue;
            if (l <= le[x] && rg[x] <= r) {
                qr.push_back({r, l, id});
                id = -1;
            }
        }
    }

    std::sort(op.begin(), op.end());
    std::sort(qr.begin(), qr.end());

    int t = 0;
    for (auto [r, l, id] : qr) {
        while (t < op.size() && op[t][0] <= r) {
            auto [_, x, c] = op[t ++];
            if (x > lst[c]) {
                if (lst[c]) BIT::add(lst[c], -1);
                BIT::add(x, +1);
                lst[c] = x;
            }
        }
        ans[id] = BIT::ask(r) - BIT::ask(l - 1);
    }

    for (auto [y, x, c] : op) {
        if (lst[c]) {
            BIT::add(lst[c], -1);
            lst[c] = 0;
        }
    }

    for (int v : G.table[u]) {
        if (ban[v]) continue;
        tot_sz = sz[v], tot_rt = 0;
        GetRoot(v, u), solve(tot_rt);
    }
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);

    std::cin >> n >> m;

    for (int i = 1; i <= n; i ++) {
        std::cin >> col[i];
    }

    G.init(n);
    for (int i = 1; i < n; i ++) {
        int x, y;
        std::cin >> x >> y;

        G.add_edge(x, y), G.add_edge(y, x);
    }

    for (int i = 1; i <= m; i ++) {
        int l, r, x;
        std::cin >> l >> r >> x;

        qry[x].push_back({l, r, i});
    }

    tot_sz = n, tot_rt = 0;
    GetRoot(1, 0), solve(tot_rt);

    for (int i = 1; i <= m; i ++) {
        std::cout << ans[i] << '\n';
    }

    return 0;
}

/**
 *  心中无女人
 *  比赛自然神
 *  模板第一页
 *  忘掉心上人
**/

算法二：Kruskal 重构树

考虑与 xx 在同一个连通块的节点 yy，显然要满足从 xx 到 yy 的简单路径上经过的所有点中，编号最小值 ≥l\geq l，编号最大值 ≤r\leq r。

考虑给树边赋上两种不同的权值。第一类权值设为两端点编号的较小值，则从 xx 到 yy 只能经过第一类权值 ≥l\geq l 的边；第二类权值设为两端点编号的较大值，则从 xx 到 yy 只能经过第二类权值 ≤r\leq r 的边。

发现这两部分能到达的点集，都可以使用 Kruskal 重构树进行刻画。对第一类权值建 kruskal 最大生成重构树，对第二类权值建 kruskal 最小生成重构树。此时可以发现 xx 在两部分中能到达的点集，都是一棵子树。那么 xx 在原树上能到达的点集，就是这两棵子树的交集。那么现在的任务就是要对两棵子树的交集进行数颜色。

对第一棵树进行 DSU on tree，维护第一棵子树内的点在第二棵树上的信息。现在还要考虑颜色去重的问题，对于一个颜色 cc，若其在第二棵树上有 x1,x2,⋯ ,xkx_1, x_2, \cdots, x_k 这些点，那么颜色 cc 会对这些点到根节点的树链并有 11 的贡献。有一个经典的树上差分做法：将 x1,x2,⋯ ,xkx_1, x_2, \cdots, x_k 按照 dfs 序排序。

  • 对于 1≤i≤k1 \leq i \leq k，令 xix_i 的差分数组 +1+1。
  • 对于 1≤i<k1 \leq i < k，令 LCA(xi,xi+1)\mathrm{LCA}(x_i, x_{i + 1}) 的差分数组 −1-1。

对每种颜色记录一个 std::set，用于维护每种颜色所拥有节点的 dfs 序。每次插入或删除节点，考虑其与 dfs 序上的前驱后继产生的影响即可。

时间复杂度 O(nlog⁡2n+mlog⁡n)\mathcal{O}(n \log^2 n + m \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
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
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
#include <bits/stdc++.h>

#define debug(a) std::cout << #a << "=" << (a) << ' '

using s64 = long long;
using u64 = unsigned long long;

/* 取 min */
template <class T>
inline void chmin(T &x, const T &y) {
    if (x > y) {
        x = y;
    }
}
/* 取 max */
template <class T>
inline void chmax(T &x, const T &y) {
    if (x < y) {
        x = y;
    }
}

/* ----- ----- ----- 正文 ----- ----- ----- */

const int N = 100100;
const int SIZE = N * 2;

int n, m;
int col[N];

struct Edge {
    int x, y, z;
} e[N];

int fa[SIZE];
int get(int x) {
    return fa[x] == x ? x : fa[x] = get(fa[x]);
}

struct Tree {
    int t;
    int val[SIZE];
    int son[SIZE][2], anc[18][SIZE];
    int dep[SIZE], sze[SIZE];
    int dfsClock, dfn[SIZE], idx[SIZE];

    void init() {
        t = n;
        for (int i = 1; i <= n * 2; i ++) {
            fa[i] = i;
        }
    }

    void dfs_init(int u, int fu) {
        dep[u] = dep[fu] + 1;
        sze[u] = 1;
        dfsClock ++, dfn[u] = dfsClock, idx[dfsClock] = u;
        if (u <= n) return;
        dfs_init(son[u][0], u), sze[u] += sze[son[u][0]];
        dfs_init(son[u][1], u), sze[u] += sze[son[u][1]];
    }

    int lca(int x, int y) {
        if (!x || !y) return 0;
        if (dep[x] > dep[y]) std::swap(x, y);
        for (int i = 17; i >= 0; i --)
            if (dep[x] <= dep[y] - (1 << i)) y = anc[i][y];
        if (x == y) return x;
        for (int i = 17; i >= 0; i --)
            if (anc[i][x] ^ anc[i][y]) x = anc[i][x], y = anc[i][y];
        return anc[0][x];
    }

    void deal() {
        dfs_init(t, 0);
        for (int j = 1; j <= 17; j ++) {
            for (int i = 1; i <= t; i ++) {
                anc[j][i] = anc[j - 1][anc[j - 1][i]];
            }
        }
    }
} T1, T2;

void build1() {
    for (int i = 1; i < n; i ++) {
        e[i].z = std::min(e[i].x, e[i].y);
    }
    std::sort(e + 1, e + n, [&] (Edge lhs, Edge rhs) -> bool {
        return lhs.z > rhs.z;
    });

    T1.init();

    for (int i = 1; i < n; i ++) {
        auto [x, y, z] = e[i];

        int p = get(x), q = get(y);

        int u = ++ T1.t;
        T1.val[u] = z;
        T1.son[u][0] = p, T1.son[u][1] = q;
        T1.anc[0][p] = T1.anc[0][q] = u;
        fa[p] = fa[q] = u;
    }

    T1.deal();
}

void build2() {
    for (int i = 1; i < n; i ++) {
        e[i].z = std::max(e[i].x, e[i].y);
    }
    std::sort(e + 1, e + n, [&] (Edge lhs, Edge rhs) -> bool {
        return lhs.z < rhs.z;
    });

    T2.init();

    for (int i = 1; i < n; i ++) {
        auto [x, y, z] = e[i];

        int p = get(x), q = get(y);

        int u = ++ T2.t;
        T2.val[u] = z;
        T2.son[u][0] = p, T2.son[u][1] = q;
        T2.anc[0][p] = T2.anc[0][q] = u;
        fa[p] = fa[q] = u;
    }

    T2.deal();
}

std::set<int> g[N];

namespace BIT {
    int c[SIZE];

    void add(int x, int y) {
        if (!x) return;
        for (; x <= T2.dfsClock; x += x & -x) {
            c[x] += y;
        }
    }

    int ask(int x) {
        int ans = 0;
        for (; x; x -= x & -x) {
            ans += c[x];
        }
        return ans;
    }

    int get(int x) {
        int l = T2.dfn[x], r = T2.dfn[x] + T2.sze[x] - 1;
        return ask(r) - ask(l - 1);
    }
}

void add(int x) {
    int c = col[x];
    auto it = g[c].lower_bound(T2.dfn[x]);
    int net = T2.idx[*it],
        pre = T2.idx[*std::prev(it)];
    BIT::add(T2.dfn[x], +1);
    BIT::add(T2.dfn[T2.lca(pre, x)], -1);
    BIT::add(T2.dfn[T2.lca(x, net)], -1);
    BIT::add(T2.dfn[T2.lca(pre, net)], +1);
    g[c].insert(T2.dfn[x]);
}

void dec(int x) {
    int c = col[x];
    auto it = g[c].lower_bound(T2.dfn[x]);
    int pre = T2.idx[*std::prev(it)],
        net = T2.idx[*std::next(it)];
    BIT::add(T2.dfn[x], -1);
    BIT::add(T2.dfn[T2.lca(pre, x)], +1);
    BIT::add(T2.dfn[T2.lca(x, net)], +1);
    BIT::add(T2.dfn[T2.lca(pre, net)], -1);
    g[c].erase(it);
}

std::pair<int, int> find(int l, int r, int x) {
    int p = x;
    for (int i = 17; i >= 0; i --) {
        if (T1.anc[i][p] && T1.val[T1.anc[i][p]] >= l) {
            p = T1.anc[i][p];
        }
    }
    int q = x;
    for (int i = 17; i >= 0; i --) {
        if (T2.anc[i][q] && T2.val[T2.anc[i][q]] <= r) {
            q = T2.anc[i][q];
        }
    }
    return {p, q};
}

std::vector< std::pair<int, int> > qry[SIZE];
int ans[N];

void change(int u, int opt) {
    if (u <= n) opt ? add(u) : dec(u);
    if (T1.son[u][0]) change(T1.son[u][0], opt);
    if (T1.son[u][1]) change(T1.son[u][1], opt);
}

void solve(int u) {
    if (u > n) {
        if (T1.sze[T1.son[u][0]] < T1.sze[T1.son[u][1]]) {
            std::swap(T1.son[u][0], T1.son[u][1]);
        }
        solve(T1.son[u][1]), change(T1.son[u][1], 0);
        solve(T1.son[u][0]), change(T1.son[u][1], 1);
    } else {
        add(u);
    }

    for (auto [v, id] : qry[u]) {
        ans[id] = BIT::get(v);
    }
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);

    std::cin >> n >> m;

    for (int i = 1; i <= n; i ++) {
        std::cin >> col[i];
    }

    for (int i = 1; i < n; i ++) {
        int x, y;
        std::cin >> x >> y;
        e[i] = {x, y, 0};
    }

    build1();
    build2();

    for (int i = 1; i <= n; i ++) {
        g[i] = {0, T2.dfsClock + 1};
    }

    for (int i = 1; i <= m; i ++) {
        int l, r, x;
        std::cin >> l >> r >> x;

        auto [p, q] = find(l, r, x);

        qry[p].push_back({q, i});
    }

    solve(T1.t);

    for (int i = 1; i <= m; i ++) {
        std::cout << ans[i] << '\n';
    }

    return 0;
}

/**
 *  心中无女人
 *  比赛自然神
 *  模板第一页
 *  忘掉心上人
**/