「Ynoi2011」成都七中
给出一棵包含 n 个点的树,每个节点有一种颜色 c_i。
有 m 次查询,每次查询给出三个参数 l, r, x,表示询问只保留编号在 [l, r] 范围内的点时,x 所在连通块的颜色种类数。
数据范围:1 \leq n, m \leq 10^5,1 \leq c_i \leq n,1 \leq l \leq x \leq r \leq n。
时空限制:1s / 250MiB。
Solution
算法一:点分治
考虑与 x 在同一个连通块的节点 y,显然要满足从 x 到 y 的简单路径上经过的所有点中,编号最小值 \geq l,编号最大值 \leq r。
如果可以从 x 只经过编号在 [l, r] 内的点到达 x',则询问 l, r, x 可以等价于询问 l, r, x'(相当于从 x' 出发)。
如果不能从 x 只经过编号在 [l, r] 内的点到达 x',则整棵树可以被 x' 划分成若干个连通块,由于 x 不能到达 x',故 x 无法穿过 x' 到达其他的连通块。
这启发我们进行点分治,对于当前的分治中心 \mathrm{rt},我们处理出 \mathrm{rt} 到达当前连通块每个点 i 的简单路径上,编号最小值 \mathrm{le}_i 和编号最大值 \mathrm{rg}_i。
对于一个询问 l, r, x,若可以从 \mathrm{rt} 只经过编号在 [l, r] 内的点到达 x(即 l \leq \mathrm{le}_i 且 \mathrm{rg}_i \leq r),则询问 l, r, x 相当于询问 l, r, \mathrm{rt};如果不能到达 x,则当前连通块又被 \mathrm{rt} 划分成了若干个连通块,按照点分治的模式继续分治即可。
现在的目标就是要解决询问 l, r, \mathrm{rt}。对于当前连通块内的一个点 i,若满足 l \leq \mathrm{le}_i 且 \mathrm{rg}_i \leq r,则就会对答案有一个 \mathrm{col}_i 颜色的贡献。发现这可以简单地扫描线解决,不过多赘述。
时间复杂度 \mathcal{O}(n \log^2 n + m \log n)。
#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 重构树
考虑与 x 在同一个连通块的节点 y,显然要满足从 x 到 y 的简单路径上经过的所有点中,编号最小值 \geq l,编号最大值 \leq r。
考虑给树边赋上两种不同的权值。第一类权值设为两端点编号的较小值,则从 x 到 y 只能经过第一类权值 \geq l 的边;第二类权值设为两端点编号的较大值,则从 x 到 y 只能经过第二类权值 \leq r 的边。
发现这两部分能到达的点集,都可以使用 Kruskal 重构树进行刻画。对第一类权值建 kruskal 最大生成重构树,对第二类权值建 kruskal 最小生成重构树。此时可以发现 x 在两部分中能到达的点集,都是一棵子树。那么 x 在原树上能到达的点集,就是这两棵子树的交集。那么现在的任务就是要对两棵子树的交集进行数颜色。
对第一棵树进行 DSU on tree,维护第一棵子树内的点在第二棵树上的信息。现在还要考虑颜色去重的问题,对于一个颜色 c,若其在第二棵树上有 x_1, x_2, \dots, x_k 这些点,那么颜色 c 会对这些点到根节点的树链并有 1 的贡献。有一个经典的树上差分做法:将 x_1, x_2, \dots, x_k 按照 dfs 序排序。
- 对于 1 \leq i \leq k,令 x_i 的差分数组 +1。
- 对于 1 \leq i < k,令 \mathrm{LCA}(x_i, x_{i + 1}) 的差分数组 -1。
对每种颜色记录一个 std::set,用于维护每种颜色所拥有节点的 dfs 序。每次插入或删除节点,考虑其与 dfs 序上的前驱后继产生的影响即可。
时间复杂度 \mathcal{O}(n \log^2 n + m \log n)。
#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;
}
/**
* 心中无女人
* 比赛自然神
* 模板第一页
* 忘掉心上人
**/