A(P7968 [COCI2021-2022#2] Osumnjičeni)
考虑对于一次询问直接从左往右划分段，直至当前加入的人与前面某个人的身高有交集，则新开一个段。
设 \(nx_i=j\) 表示从第 \(i\) 个人开始划分，要到第 \(j\) 个人才会出现冲突（若永远不会冲突则让 \(nx_i = n + 1\)）。一次询问相当于初始时让 \(i = l\)，需要多少次 \(i \gets nx_i\) 才能让 \(i > r\)。\(nx_i\) 的处理使用 \(\text{std::set}\) + 双指针即可。
用倍增优化跳 \(nx\) 的过程，时间复杂度 \(O(n \log n)\)。
Code
#include <iostream>
#include <set>
using namespace std;
using Pii = pair<int, int>;
const int N = 2e5 + 5, M = 18;
int n, q;
Pii a[N];
int nx[N][M];
int main () {
// freopen("sus.in", "r", stdin);
// freopen("sus.out", "w", stdout);
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i].first >> a[i].second;
}
set<Pii> s;
for (int i = 1, j = 1; i <= n; ++i) {
auto Insert = [&](Pii &a) -> bool {
auto it = s.lower_bound(a);
if (it != s.begin() && prev(it)->second >= a.first) {
return 0;
}
if (it != s.end() && it->first <= a.second) {
return 0;
}
s.insert(a);
return 1;
};
while (j <= n && Insert(a[j])) {
++j;
}
nx[i][0] = j;
s.erase(a[i]);
}
nx[n + 1][0] = n + 1;
for (int k = 1; k < M; ++k) {
for (int i = 1; i <= n + 1; ++i) {
nx[i][k] = nx[nx[i][k - 1]][k - 1];
}
}
cin >> q;
for (int l, r; q--; ) {
cin >> l >> r;
int res = 0;
for (int k = M - 1; ~k; --k) {
if (nx[l][k] <= r) {
l = nx[l][k];
res |= (1 << k);
}
}
cout << res + 1 << '\n';
}
return 0;
}
B(「JOISC 2017 Day 1」港口设施)
问题相当于将 \(n\) 条形如 \([l_i, r_i]\) 线段划分到两个集合，使两个集合内都没有线段严格相交（相交且不包含），求方案数。
首先暴力做法是枚举两条线段，如果它们严格相交就连一条边，然后二分图染色，如果有解则答案是 \(2\) 的连通块数次幂。
考虑优化建图，先对所有线段按 \(l_i\) 排序，对于 \(i < j\)，若 \(r_i \in [l_j, r_j]\) 则图上有一条边 \((i, j)\)。注意到若 \([l_i, r_i]\) 和 \([l_j, r_j]\) 同时包含一个 \(r_k\)，则它们在染色时一定同色。对于同色或异色的限制，考虑用拓展域并查集的 \(\text{Unite}\) 和 \(\text{Enemy}\) 操作维护。
从右往左添加线段 \([l_i, r_i]\)，用 \(\text{std::set}\) 维护当前加入的所有线段（我们在维护时保证这些线段不会有包含关系），我们不断找到一条 \(l_j(j > i)\) 最大的线段 \([l_j, r_j]\)，并考察两条线段的关系：
-
若两条线段相离，则当前线段 \([l_i, r_i]\) 加入时和后面的线段不会新增任何限制，退出即可。
-
若两条线段严格相交，考察是否存在 \(k < i\) 使得 \(r_k\) 落在它们交的区域，即 \(r_k \in [r_i, l_j]\)，这个用树状数组维护。
- 若存在，则根据前面的结论我们可以 \(\text{Unite}(i, j)\)，同时两条线段严格交，所以我们又可以 \(\text{Enemy}(i, j)\)，此时一定无解，输出 \(0\) 即可。
- 若不存在，先 \(\text{Enemy}(i, j)\)，考虑由于 \(j\) 以后相交的线段一定在 \(j\) 时刻用 \(\text{Unite}\) 操作刻画过，无需考虑。与 \(i\) 相离的线段也无需考虑。被 \(i\) 包含的线段一定被 \(j\) 包含，矛盾，也无需考虑。直接退出即可。
-
若两条线段是包含关系，由于 \(l_i < l_j\)，则一定是 \(i\) 包含 \(j\)。同样考察是否存在 \(k < i\) 使得 \(r_k\) 落在它们交的区域。
- 若存在，则我们可以 \(\text{Unite}(i, j)\)，由于 \(i\) 包含 \(j\)，在 \(i\) 之前不存在只与 \(j\) 相交不与 \(i\) 相交的线段。删除当前 \(j\) 并继续考察下一个 \(j\) 即可。
- 若不存在，\(j\) 与 \(i\) 之前的线段无限制，与 \(i\) 之后的线段的限制考虑过。删除当前 \(j\) 并继续考察下一个 \(j\) 即可。
最后检查并查集表示的信息是否冲突，算并查集连通块数即可。时间复杂度 \(O(n \log n)\)。单调栈预处理树状数组的部分可做到 \(O(n)\)。
Code
#include <iostream>
#include <algorithm>
#include <numeric>
#include <set>
using namespace std;
using Pii = pair<int, int>;
const int N = 1e6 + 5;
const int Mod = 1e9 + 7;
int n, fa[N * 2], c[N * 2];
Pii a[N];
struct L {
Pii a;
int id;
bool operator< (L l) const {
return a < l.a;
}
};
int Find (int x) {
if (fa[x] == x) return x;
return fa[x] = Find(fa[x]);
}
void Unite (int x, int y) { fa[Find(x)] = Find(y), fa[Find(x + n)] = Find(y + n); }
void Enemy (int x, int y) { fa[Find(x + n)] = Find(y), fa[Find(y + n)] = Find(x); }
void Add (int x, int y) {
for (; x <= n * 2; x += (x & -x)) {
c[x] += y;
}
}
int Query (int l, int r) {
int res = 0;
for (--l; l; l -= (l & -l)) {
res -= c[l];
}
for (; r; r -= (r & -r)) {
res += c[r];
}
return res;
}
int main () {
// freopen("usd.in", "r", stdin);
// freopen("usd.out", "w", stdout);
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i].first >> a[i].second;
Add(a[i].second, 1);
}
sort(a + 1, a + n + 1);
iota(fa + 1, fa + n * 2 + 1, 1);
set<L> s;
for (int i = n; i; --i) {
auto it = s.lower_bound((L){{a[i].second + 1, 0}, 0});
Add(a[i].second, -1);
L tmp = (L){{a[i].first, a[i].second}, i};
[&]() -> void {
s.insert(tmp);
for (set<L>::iterator it; (it = s.find(tmp)) != --s.end(); ) {
if (next(it)->a.second <= a[i].second) {
if (Query(next(it)->a.first, next(it)->a.second)) {
Unite(i, next(it)->id);
}
s.erase(next(it));
continue;
}
if (next(it)->a.first >= a[i].second) {
return;
}
Enemy(i, next(it)->id);
if (Query(next(it)->a.first, a[i].second)) {
Unite(i, next(it)->id);
tmp.a = (Pii){a[i].first, next(it)->a.second};
s.erase(it, next(it, 2));
s.insert(tmp);
}
else {
break;
}
}
}();
}
for (int i = 1; i <= n; ++i) {
if (Find(i) == Find(i + n)) {
cout << 0 << '\n';
return 0;
}
}
int cnt = 0;
for (int i = 1; i <= n * 2; ++i) {
cnt += fa[i] == i;
}
cnt = cnt / 2;
int ans = 1;
while (cnt--) {
ans = ans * 2 % Mod;
}
cout << ans << '\n';
return 0;
}
C(CF103E Buying Sets)
题意：有 \(n\) 个集合 \(U_{1 \sim n}\) 和 \(n\) 种数字 \(1 \sim n\)，每个集合包含若干数字，第 \(i\) 个集合有一个权值 \(v_i\)，要求选出一些（数量任意）集合 \(U_{t_1}, U_{t_2}, \ldots, U_{t_k}\)，使得 \(|\bigcup\limits_{i = 1}^{k} U_{t_i}| = k\)，最小化 \(\sum\limits_{i = 1}^{k} v_{t_i}\)，保证存在一个 \(1 \sim n\) 的排列 \(p_{1 \sim n}\)，使得 \(i \in U_{p_i}\)，\(v_i\) 可正可负。
首先根据 Hall 定理，我们有对于任意由 \(S\) 构成的集族 \(\mathcal{M}\)，有 \(|\bigcup\limits_{S \in \mathcal{M}} S| \ge |\mathcal{M}|\)。
将权值取反，\(v_i \gets -v_i\)，我们可以将最小权值转化为最大权值。然后对于所有集合，权值总和一定，将最大化选出的权值转化为最小化不选的权值，建立最小割模型。
具体而言，左部点表示集合 \(U_{1 \sim n}\)，右部点表示数字 \(1 \sim n\)，\(S\) 向左部点 \(i\) 连边，权值为 \(v_i + \alpha\)，右部点向 \(T\) 连边，权值为 \(\alpha\)，若 \(j \in U_{i}\)，则将左部点 \(i\) 向右部点 \(j\) 连边，权值为 \(\alpha\)，其中 \(\alpha\) 是一个极大数。
容易发现割集合连向数字的边不严格优于直接割数字连向 \(T\) 的边，所以这些边是不会割的。由于 \(\alpha\) 极大，可以看作先最小化 \(\alpha\) 的系数，再最小化常数，也就是第一步要最小化割边的数量。设最小割割边数为 \(|E|\)，容易构造出割 \(n\) 条边的方案，因此 \(|E| \le n\)，又因为 \(|\bigcup\limits_{S \in \mathcal{M}} S| \ge |\mathcal{M}| \iff (n - |\mathcal{M}|) + |\bigcup\limits_{S \in \mathcal{M}} S| \ge n\)，由于左部点和右部点之间的边不会割，这就说明了 \(|E| \ge n\)，因此 \(|E| = n\)。
跑最小割即可，时间复杂度不作分析，反正是能过的。
Code
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
using LL = long long;
const int iMax = 1e9;
const LL Inf = 1e18;
namespace Dinic {
const int N = 605;
struct E {
int v, w, id;
};
int n, s, t;
int dis[N];
vector<E> e[N];
vector<E>::iterator now[N];
bool Bfs () {
fill(dis + 1, dis + n + 1, -1), dis[s] = 0;
queue<int> q;
for (q.push(s); !q.empty(); q.pop()) {
int u = q.front();
for (auto i : e[u]) {
int v = i.v, w = i.w;
if (w && dis[v] == -1) {
dis[v] = dis[u] + 1;
q.push(v);
}
}
}
return dis[t] != -1;
}
LL Dfs (int u, LL d) {
if (u == t) return d;
LL res = 0;
for (auto it = now[u]; it != e[u].end() && d; ++it) {
now[u] = it;
int v = it->v, &w = it->w, id = it->id;
if (dis[v] == dis[u] + 1 && w) {
LL r = Dfs(v, min(d, 0ll + w));
if (!r) dis[v] = -1;
res += r;
d -= r;
w -= r;
e[v][id].w += r;
}
}
return res;
}
void Add_edge (int u, int v, int w) {
e[u].push_back((E){v, w, int(e[v].size())});
e[v].push_back((E){u, 0, int(e[u].size()) - 1});
}
LL Max_flow () {
LL ans = 0;
while (Bfs()) {
for (int i = 1; i <= n; ++i) {
now[i] = e[i].begin();
}
ans += Dfs(s, Inf);
}
return ans;
}
};
int main () {
// freopen("pois.in", "r", stdin);
// freopen("pois.out", "w", stdout);
cin.tie(0)->sync_with_stdio(0);
int n;
cin >> n;
Dinic::n = n * 2 + 2, Dinic::s = n * 2 + 1, Dinic::t = n * 2 + 2;
for (int i = 1; i <= n; ++i) {
int c;
cin >> c;
for (int x; c--; ) {
cin >> x;
Dinic::Add_edge(i, x + n, iMax);
}
}
LL sum = 0;
for (int i = 1, v; i <= n; ++i) {
cin >> v, v = -v;
sum += v;
Dinic::Add_edge(Dinic::s, i, v + iMax);
}
for (int i = n + 1; i <= n * 2; ++i) {
Dinic::Add_edge(i, Dinic::t, iMax);
}
cout << -(sum - (Dinic::Max_flow() - 1ll * n * iMax)) << '\n';
return 0;
}