https://codeforces.com/contest/1996/problem/G
题目大意
给出 $n \le 2 \cdot 10^5$ 个点的一个简单环，给出 $m \le 2 \cdot 10^5$ 组点。要求选最少的边，使得 $m$ 组点之间，都可以通过选的边连通。给的每组点 $u < v$。
简要题解
一般环形问题先想直线问题，再想断开环。
直线问题非常好解决，相当于求 $m$ 个线段的覆盖。
断开环。注意到最多只需要 $n - 1$ 条边，因此我们直接枚举这个断开的位置，然后动态的维护覆盖。注意到一组线段 $u \to v$ 如果切点在 $u, v$ 之间则必然需要选绕过起点终点的方案，否则必然选 $u \to v$ 之间的覆盖（因为切点在外面会切断另一种选法），因此其实切点确定了，每组关系选择的方案也就确定了。
发现不下传标记的线段树可以维护这个覆盖，然后就做完了。（同样的线段树用于矩形面积交、并的扫描线线段树）
复杂度
$T$：$O(nlogn)$
$S$：$O(n)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
// enumerate the split point!
struct SegT {
int n;
vector<int> cover, sum;
SegT(int n) : n(n), cover(n << 2), sum(n << 2) {}
int L, R, V;
void update_(int o, int l, int r) {
if (L <= l && r <= R) {
cover[o] += V;
if (cover[o]) sum[o] = r - l + 1;
else {
if (l == r) {
sum[o] = 0;
} else {
sum[o] = sum[o << 1] + sum[o << 1 | 1];
}
}
return;
}
int mid = (l + r) >> 1;
if (L <= mid) update_(o << 1, l, mid);
if (mid < R) update_(o << 1 | 1, mid + 1, r);
if (!cover[o]) sum[o] = sum[o << 1] + sum[o << 1 | 1];
}
void update(int l, int r, int v) {
L = l; R = r; V = v;
update_(1, 0, n - 1);
}
};
void solve() {
int n, m; cin >> n >> m;
vector<vector<int>> st(n), ed(n);
SegT segt(n);
int u, v;
for (int i = 0; i < m; i++) {
cin >> u >> v; u--; v--;
st[u].push_back(v);
ed[v].push_back(u);
segt.update(u, v - 1, 1);
}
int ans = segt.sum[1];
for (int i = 0; i < n - 1; i++) {
for (int r : st[i]) {
segt.update(i, r - 1, -1);
segt.update(r, n - 1, 1);
if (i) {
segt.update(0, i - 1, 1);
}
}
for (int l : ed[i]) {
segt.update(i, n - 1, -1);
if (l) {
segt.update(0, l - 1, -1);
}
segt.update(l, i - 1, 1);
}
cmin(ans, segt.sum[1]);
}
cout << ans << '\n';
}
int main() {
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
做法 2
更进一步的，我们考虑对于某一个答案的覆盖，一些段是由线段 $a_i, b_i$ 覆盖的，而剩下的所有是由 $0 \to a_i$ 和 $b_i \to n$ 覆盖的，注意这里两种覆盖是全集，因此一组 $a_i \to b_i$ 的覆盖的集合就可以表示选取的方案。同样的其补集，一组被切断的边同样可以表示这个覆盖。考虑这个覆盖有多个不选的边 $a_1, a_2, \cdots$ 则我们说，这些所有不选边对应的割边方案一致。
证明：考虑割断 $a_1$ 位置的集合 $S_1$，割断 $a_2$ 的集合 $S_2$。割断 $a_1$ 时 $a_2$ 也是不选的。考虑 $e \in S_1$ 但 $e \notin S_2$。这里由两个位置都不选，可以得出 $e$ 应该不覆盖 $a_1$ 和 $a_2$，否则这两段的覆盖关系必然是相反的。但从 $e \in S_1$ 但 $e \notin S_2$，可以得出 $e$ 覆盖 $a_1$ 不覆盖 $a_2$。矛盾。
于是我们只要统计每个位置的集合出现的频率，选最高的频率即可。
这里就用到了 Xor Hash。给每个段一个随机值，则集合就是其 xor hash。64 位随机值的容错率已经足够了。
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
void solve() {
int n, m; cin >> n >> m;
vector<ULL> x(n);
int u, v;
for (int i = 0; i < m; i++) {
cin >> u >> v; u--; v--;
ULL h = rnd_64();
x[u] ^= h;
x[v] ^= h;
}
map<ULL, int> cnt;
ULL cur = 0;
for (int i = 0; i < n; i++) {
cur ^= x[i];
cnt[cur]++;
}
int mx = 0;
for (auto&& [v, c] : cnt) {
cmax(mx, c);
}
cout << n - mx << '\n';
}
int main() {
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: D. Maximize the Root - Educational Codeforces Round 168