对于一些对一定区间的操作, 将区间存入线段树节点的 std::vector 容器上, 然后在线段树上 dfs, 计算每一状态.
例: P5787 二分图 /【模板】线段树分治
将边按存在的时间加入线段树, 注意实际取不到 \(r\), 这里我的线段树是 1-index 的, 所以直接 l++ 了.
使用了可撤销并查集, 每次操作是 \(O(\log n)\) 的, 又每段分成 \(O(\log k)\) 个节点, 故复杂度为 \(O(m\log m \log n)\).
const int N = 1e5 + 10;
vector<vector<array<int, 2>>> tr(N << 2);
UDSU ds(N * 2);
void modify(int idx, int l, int r, int ql, int qr, const array<int, 2> &op) {
if (ql <= l && qr >= r) {
tr[idx].push_back(op);
return;
}
int mid = (l + r) >> 1;
if (ql <= mid)
modify(idx << 1, l, mid, ql, qr, op);
if (qr > mid)
modify(idx << 1 | 1, mid + 1, r, ql, qr, op);
}
int n;
void solve(int idx, int l, int r) {
int len = tr[idx].size();
bool yes = 1;
for (int i = 0; i < len; i++) {
int u = tr[idx][i][0], v = tr[idx][i][1];
if (ds.root(u + n) == ds.root(v + n)) {
yes = 0;
for (int j = i; j > 0; j--) {
ds.undo(), ds.undo();
}
for (int j = l; j <= r; j++) {
cout << "No" << '\n';
}
break;
}
ds.bind(u, v + n), ds.bind(u + n, v);
}
if (yes) {
if (l == r) {
cout << "Yes" << '\n';
} else {
int mid = (l + r) >> 1;
solve(idx << 1, l, mid);
solve(idx << 1 | 1, mid + 1, r);
}
for (int i = 0; i < len; i++) {
ds.undo(), ds.undo();
}
}
}
void solve() {
int m, k;
cin >> n >> m >> k;
for (int i = 0; i < m; i++) {
int x, y, l, r;
cin >> x >> y >> l >> r;
l++;
modify(1, 1, k, l, r, {x, y});
}
solve(1, 1, k);
}例: CF1814F Communication Towers
可以理解为在 \(l_i \sim r_i\) 时刻才能将点 \(i\) 加入图中, 那么直接线段树分治.
然后用类似懒标记的思想维护一个 ans 数组, DSU 的 undo 之前先在 \(1\) 所在的 ans[root] +1, 然后把边 \(u \to v\) 删掉时就 ans[u] += ans[v], 加边 \(u \to v\) 时先判断下是否本就在同一区间, 然后令 ans[u] -= ans[v], 防止 ans[v] 原本的值影响 ans[u].
当然这里直接把边加入线段树更好写 solve, 但是这里 xkm 太懒就直接加的点.
复杂度分析同上喵.
// 修改过的UDSU
class UDSU {
public:
std::vector<int> f, size;
std::stack<std::array<int, 2>> sta;
std::vector<int> ans;
UDSU(std::size_t size) : f(size + 1), size(size + 1), ans(size + 1) {
std::iota(f.begin(), f.end(), 0);
}
int root(int u) {
return f[u] == u ? u : root(f[u]);
}
void bind(int u, int v) {
u = root(u), v = root(v);
if (size[u] > size[v])
std::swap(u, v);
ans[u] -= ans[v];
sta.push({u, size[v]});
f[u] = v;
if (size[u] == size[v])
size[v]++;
}
void undo() {
auto [u, sizev] = sta.top();
sta.pop();
ans[u] += ans[f[u]];
size[f[u]] = sizev, f[u] = u;
}
};
UDSU dsu(N);
vector<int> live(N);
vector<vector<int>> gra(N), tr(N << 2);
void add(int idx, int l, int r, int ql, int qr, int x) {
if (ql <= l && qr >= r) {
tr[idx].push_back(x);
return;
}
int mid = (l + r) >> 1;
if (ql <= mid)
add(idx << 1, l, mid, ql, qr, x);
if (qr > mid)
add(idx << 1 | 1, mid + 1, r, ql, qr, x);
}
void solve(int idx, int l, int r) {
int cnt = 0;
for (auto u : tr[idx]) {
live[u] = 1;
}
for (auto u : tr[idx]) {
for (auto v : gra[u]) {
if (live[v] && dsu.root(u) != dsu.root(v)) {
cnt++;
dsu.bind(u, v);
}
}
}
if (l != r) {
int mid = (l + r) >> 1;
solve(idx << 1, l, mid);
solve(idx << 1 | 1, mid + 1, r);
}
dsu.ans[dsu.root(1)]++;
while (cnt--) {
dsu.undo();
}
for (auto u : tr[idx]) {
live[u] = 0;
}
}
void solve() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
int l, r;
cin >> l >> r;
add(1, 1, N, l, r, i);
}
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
gra[u].push_back(v);
gra[v].push_back(u);
}
solve(1, 1, N);
for (int i = 1; i <= n; i++) {
if (dsu.ans[i])
cout << i << ' ';
}
cout << '\n';
}例: CF1681F Unique Occurrences
考虑每个边权为 \(x\) 的边产生的贡献:
单独去掉边权为 \(x\) 的边后, 剩下一堆连通块, 边权为 \(x\) 的边会连接两个连通块, 贡献就是连通块大小相乘.
线段树分治, 将边权为 \(x\) 的边加到 \(1 \sim x – 1\), \(x + 1 \sim n\) 区间上, 那么 dfs 到 \(x \sim x\) 区间时, 就刚好只剩边权为 \(x\) 的边没连, 计算贡献即可.
// 秩改为大小而非深度
class UDSU {
public:
std::vector<int> f, size;
std::stack<std::array<int, 2>> sta;
UDSU(std::size_t size) : f(size + 1), size(size + 1, 1) {
std::iota(f.begin(), f.end(), 0);
}
int root(int u) {
return f[u] == u ? u : root(f[u]);
}
void bind(int u, int v) {
u = root(u), v = root(v);
if (size[u] > size[v])
std::swap(u, v);
sta.push({u, size[v]});
f[u] = v;
size[v] += size[u];
}
void undo() {
auto [u, sizev] = sta.top();
sta.pop();
size[f[u]] = sizev, f[u] = u;
}
} dsu(N);
vector<vector<int>> tr(N << 2);
vector<vector<array<int, 2>>> gra(N + 1);
LL ans = 0;
void add(int idx, int l, int r, int ql, int qr, int x) {
if (ql <= l && qr >= r) {
tr[idx].push_back(x);
return;
}
int mid = (l + r) >> 1;
if (ql <= mid)
add(idx << 1, l, mid, ql, qr, x);
if (qr > mid)
add(idx << 1 | 1, mid + 1, r, ql, qr, x);
}
void solve(int idx, int l, int r) {
int cnt = 0;
for (auto x : tr[idx]) {
for (auto [u, v] : gra[x]) {
cnt++, dsu.bind(u, v);
}
}
if (l == r) {
for (auto [u, v] : gra[l]) {
ans += (LL)dsu.size[dsu.root(u)] * dsu.size[dsu.root(v)];
}
} else {
int mid = (l + r) >> 1;
solve(idx << 1, l, mid);
solve(idx << 1 | 1, mid + 1, r);
}
while (cnt--) {
dsu.undo();
}
}
vector<int> have(N + 1);
void solve() {
int n;
cin >> n;
for (int i = 1; i < n; i++) {
int u, v, x;
cin >> u >> v >> x;
gra[x].push_back({u, v});
if (!have[x]) {
if (x != 1)
add(1, 1, n, 1, x - 1, x);
if (x != n)
add(1, 1, n, x + 1, n, x);
have[x] = 1;
}
}
solve(1, 1, n);
cout << ans << '\n';
}