那快把题端上来吧（三）

CF1814F Communication Towers

边在某种情况下可通过，可以看做在某种情况下出现，且出现时间为端点值域的交集，考虑线段树分治。
递归到叶子节点后，和 \(1\) 在同一个连通块内的全部合法，但遍历赋值太劣了，于是我们考虑打标记。
记 \(tag[x]\) 为 \(x\) 在几个叶子节点与 \(1\) 在同一个连通块。
只需要给 \(1\) 所在连通块的根标记 \(+1\) ，然后每次撤销时下传标记。
但是，标记并非一定要下传，如果有个连通块在中途接上另一个，然后撤销就会白嫖走标记。
所以我们只维护相连这段时间标记的增量下传。
具体的，如果 \(y\) 要作为 \(x\) 的根，就将 \(tag[x]\) 减去 \(tag[y]\) ，撤销时再加回来，就可以维护出他们在同一个连通块内时根的增量。

点击查看

#include <bits/stdc++.h>
#define lep(i, a, b) for (int i = a; i <= b; ++i)
#define rep(i, a, b) for (int i = a; i >= b; --i)const int _ = 4e5 + 7;
const int V = 2e5;
typedef long long ll;
typedef double db;
typedef std::pair<int, int> PII;int n, m, l[_], r[_], fa[_], sz[_], tag[_], u[_], v[_], stk[_], top;
std::vector <int> op[_ << 2];int fnd(int x) { return fa[x] == x ? x : fnd(fa[x]); }
void mrg(int x, int y) {if ((x = fnd(x)) == (y = fnd(y))) return;if (sz[x] > sz[y]) std::swap(x, y);tag[x] -= tag[y], fa[x] = y, sz[y] += sz[x], stk[++top] = x;
}
void Back(int bot) { int x; while (top != bot) x = stk[top--], tag[x] += tag[fa[x]], sz[fa[x]] -= sz[x], fa[x] = x; }
#define ls p << 1
#define rs p << 1 | 1
#define md ((s + t) >> 1)
void Mdy(int l, int r, int s, int t, int v, int p) {if (r < s or t < l or l > r) return;if (l <= s and t <= r) return op[p].push_back(v), void();Mdy(l, r, s, md, v, ls), Mdy(l, r, md + 1, t, v, rs);
}
void Qry(int s, int t, int p) { int bot = top;for (int x : op[p]) mrg(u[x], v[x]);if (s == t) ++tag[fnd(1)];else { Qry(s, md, ls); Qry(md + 1, t, rs); }Back(bot);
}
#undef ls
#undef rs
#undef mdint main() {std::ios::sync_with_stdio(false);std::cin >> n >> m;lep(i, 1, n) std::cin >> l[i] >> r[i], fa[i] = i, sz[i] = 1;int x, y;lep(i, 1, m) {std::cin >> x >> y, u[i] = x, v[i] = y;if (l[x] > l[y]) std::swap(x, y);Mdy(l[y], std::min(r[x], r[y]), 1, V, i, 1);}Qry(1, V, 1);lep(i, 1, n) if (tag[i] > 0) std::cout << i << ' ';std::cout << '\n';return 0;
}