没做完。
A. Coloring
有 \(n\) 个元素，第 \(i\) 个元素有价值 \(w_i\)，颜色 \(c_i\)。给定 \(s\)，初始时只有 \(c_s=1\)，其余 \(c_i\) 均为 \(0\)。
可以进行任意操作：选择一个 \(1 \le i \le n\)，花费 \(p_i\) 的代价令 \(c_{a_i} \gets c_i\)。
你的收益是最后 \(c_i = 1\) 的 \(w_i\) 之和减去操作的花费，求最大收益。
\(1 \le s \le n \le 5 \times 10^3\)，\(-10^9 \le w_i \le 10^9\)，\(0 \le p_i \le 10^9\)，\(1 \le a_i \le n\)，\(a_i \neq i\)。
很炫酷的题。
整个图的结构是基环树。不妨假设 \(s\) 在环上，考虑变换，⼀定是环上连续⼀段 \(0\) ⼀段 \(1\) 变换，然后随着环上 \(01\) 变换，每次染到环上某个点时都可以往子树内然一段，于是子树里也会变成 \(01\) 分层的情况。
子树里如果 \(01\) 分成了最多 \(k\) 次，那么环上至少 \(01\) 变换 \(k\) 次。首先可以把子树部分的代价 DP 出来，即设 \(f(u,i)\) 表示 \(u\) 子树内分出至多 \(i\) 层时的答案，利用前缀 \(\max\) 转移，可以做到 \(\mathcal{O}(n^2)\)。
然后考虑环上，记 \(r_i\) 为环上点 \(i\) 的变换次数。通过手玩可以得到结论：从 \(s\) 开始按照边的顺序，\(r\) 单调不增且极差 \(\le 2\)。因此我们可以枚举变换次数，在环上 DP 即可，具体来说可以设 \(dp(i,j)(0 \le j \le 2)\) 表示环上第 \(i\) 的点的变换次数为 \(r_s - j\) 时的最大值，这部分时间复杂度 \(\mathcal{O}(n)\)。总时间复杂度 \(\mathcal{O}(n^2)\)。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair <LL, LL> pi;
#define fi first
#define se second
constexpr int N = 5e3 + 5;
constexpr LL inf = 1e18;
bool Mbe;
int n, s, a[N], vis[N], cir[N], len;
vector <int> e[N];
LL w[N], p[N];
LL f[N][N], g[N][N];
void chkmx(LL &x, LL y) {
x = x > y ? x : y;
}
void dfs(int u) {
for (auto v : e[u]) {
if (vis[v]) continue;
dfs(v);
for (int i = 0; i <= n; i++) {
f[u][i] += g[v][i];
}
}
for (int i = 0; i <= n; i++) {
f[u][i] += w[u] * (i & 1) - p[u] * i;
g[u][i] = f[u][i];
if (i) {
chkmx(g[u][i], g[u][i - 1]);
}
}
}
void solve() {
cin >> n >> s;
for (int i = 1; i <= n; i++)
cin >> w[i];
for (int i = 1; i <= n; i++)
cin >> p[i];
for (int i = 1; i <= n; i++) {
cin >> a[i];
e[a[i]].emplace_back(i);
}
int u = a[s];
while (!vis[u]) {
vis[u] = 1;
cir[++len] = u;
u = a[u];
}
if (!vis[s]) {
dfs(s);
cout << max(f[s][1], f[s][2]) + p[s] << "\n";
} else if (len == 2) {
dfs(s);
dfs(a[s]);
cout << max(f[s][1], max(f[s][2], f[s][1] + f[a[s]][1])) + p[s] << "\n";
} else {
reverse(cir + 1, cir + len + 1);
for (int i = 1; i <= len; i++) {
dfs(cir[i]);
}
assert(cir[1] == s);
f[s][0] = -inf;
LL ans = -inf;
static LL dp[3];
for (int i = 0; i <= n; i++) {
dp[0] = dp[1] = dp[2] = 0;
for (int j = 1; j <= len; j++) {
for (int k = 0; k < 3; k++) {
if (i + k <= n) dp[k] += f[cir[j]][i + k];
else dp[k] = -inf;
}
chkmx(dp[1], dp[2]);
chkmx(dp[0], dp[1]);
}
chkmx(ans, dp[0]);
}
cout << ans + p[s] << "\n";
}
}
bool Med;
int main() {
// fprintf(stderr, "%.9lf\n", 1.0 * (&Mbe - &Med) / 1048576.0);
ios :: sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t; t = 1;
while (t--) solve();
// cerr << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
return 0;
}
B. Binary String
给定一个 \(01\) 串 \(a_0a_1\cdots a_{n-1}\)，定义一次变换如下：对于所有 \(0 \le i < n\)，若 \(a_i = 0\) 且 \(a_{(i+1) \bmod n} = 1\)，交换 \(a_i\) 和 \(a_{(i+1) \bmod n}\)。求有多少个本质不同的 \(01\) 串满足能够从 \(a\) 变换若干次得到，答案对 \(998244353\) 取模。
\(1 \le n \le 10^7\)。
很炫酷的题。
以下的 “段” 均指长度大于 \(1\) 的 \(0\) 或 \(1\) 的连续段。手玩一下能够发现一些规律：
- 对于一个 \(0\) 段，如果其左边不和某个 \(1\) 段相邻，变换后会整体往左移动一位。
- 对于一个 \(1\) 段，如果其右边不和某个 \(0\) 段相邻，变换后会整体往右移动一位。
- 如果一个 \(0\) 段接在一个 \(1\) 段后面，那么相当于两个段相撞，变换后长度都会减 \(1\)。
这个过程会一直执行直到不存在 \(0\) 或 \(1\) 的段。每次相撞会使段的长度减 \(1\)，并且 \(0\) 段和 \(1\) 段的运动方向是相反的，所以显然变换是有限次。之后就会变成一个串在环上不断绕圈，求出这个串之后就只需要用 KMP 求一下最小整周期即可。
考虑怎么求出最后这个串。不妨假设 \(1\) 段总长度不小于 \(0\) 段总长度。
注意到这个过程和括号匹配很像阿，考虑如果不是环而是序列的话，实际上我们可以直接模拟一遍求出每个 \(0\) 连续段会在什么时候消失，以及所有 \(0\) 连续段消失后的串。而如果是环，考虑当前没有剩下的 \(1\) 去和 \(0\) 匹配的情况，由于是个环所以这些 \(0\) 会跑到末尾的位置，看起来就很烦。
那考虑规避掉这种情况。根据 Raney 引理，我们总是能找到⼀个起点位置，使得每个前缀中 \(1\) 段长度和均不小于 \(0\) 段长度和。于是直接做就行了，时间复杂度 \(\mathcal{O}(n)\)。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair <LL, LL> pi;
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define debug cerr << "[" << __LINE__ << "] "
constexpr int N = 1e7 + 5, mod = 998244353;
constexpr LL inf = 1e18;
bool Mbe;
string s;
int n, kmp[N], c[N], nc[N];
void solve() {
cin >> s;
int c0 = count(all(s), '0'), c1 = count(all(s), '1');
if (c0 < c1) {
string str = "";
for (auto i : s) str += i ^ 1;
reverse(all(str));
swap(s, str);
}
n = s.size();
s = ' ' + s;
for (int i = 1; i <= n; i++) {
if (s[i] == '0') {
string str = " ";
for (int j = 1; j <= n; j++) str += s[(i + j - 2) % n + 1];
swap(s, str);
break;
}
}
int tot = 0;
for (int i = 1; i <= n; ) {
if (s[i] == '0') {
int j = i + 1;
while (j <= n && s[j] == '1') j++;
c[++tot] = j - i - 1;
i = j;
}
}
int sum = 0, mn = 0, pos = 0;
for (int i = 1; i <= tot; i++) {
sum += c[i] - 1;
if (sum < mn) {
mn = sum;
pos = i;
}
}
for (int i = 1; i <= tot; i++) {
nc[i] = c[i];
}
for (int i = 1; i <= tot; i++) {
c[i] = nc[(i + pos - 1) % tot + 1];
}
int ans = 0;
for (int i = 1; i <= tot; i++) {
if (c[i] <= 1) continue;
int j = i, v = 0, sum = 0;
while (true) {
v += c[j] - 1;
sum++;
if (v <= 0) break;
j++;
}
ans = max(ans, sum - 1);
for (int k = i; k <= j; k++) {
c[k] = 1;
}
}
string str = " ";
for (int i = 1; i <= tot; i++) {
str += '0';
if (c[i]) str += '1';
}
int j = 0;
for (int i = 2; i <= n; i++) {
while (j && str[i] != str[j + 1]) j = kmp[j];
if (str[i] == str[j + 1]) j++;
kmp[i] = j;
}
int t = n - kmp[n];
if (n % t == 0) ans += t;
else ans += n;
cout << ans << "\n";
}
bool Med;
int main() {
// fprintf(stderr, "%.9lf\n", 1.0 * (&Mbe - &Med) / 1048576.0);
ios :: sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--) solve();
// cerr << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
return 0;
}
C. Best Carry Player 2
给定 \(x,k\)，求最小正整数 \(y\) 使得列竖式计算 \(x+y\) 时进位次数恰好为 \(k\)，若无解输出 \(-1\)。
\(1 \le T \le 10^5\)，\(1 \le x < 10^{18}\)，\(0 \le k \le 18\)。
考虑从高位往低位数位 DP，设 \(f_{i,j,k}\) 表示做到第 \(i\) 位，⼀共进了 \(j\) 位，后面是否有向前面进位，每次考虑下⼀位是否进位，以及进位或不进位情况下填的最小数字即可。时间复杂度 \(\mathcal{O}(\log^2 n)\)。
注意一些细节：由于 \(y\) 必须为正，\(k=0\) 时需要特判。以及答案可能超过 \(10^{18}\)，可以去掉末尾所有 \(0\) 再做。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair <LL, LL> pi;
typedef tuple <int, int, int> ti3;
#define fi first
#define se second
constexpr int N = 1e6 + 5, M = 20;
constexpr LL inf = 1e18;
bool Mbe;
LL p[M];
void init() {
p[0] = 1;
for (int i = 1; i <= 18; i++) p[i] = p[i - 1] * 10;
}
LL x; int k;
LL f[M][M][2];
void chkmn(LL &x, LL y) {
x = min(x, y);
}
void mian() {
cin >> x >> k;
if (k == 0) {
for (int i = 0; i <= 17; i++) {
int cur = x / p[i] % 10;
if (cur < 9) {
cout << p[i] << "\n";
return;
}
}
cout << p[18] << "\n";
return;
}
int cnt = 0;
while (x % 10 == 0) cnt++, x /= 10;
for (int i = 0; i <= 18; i++) for (int j = 0; j <= k; j++) f[i][j][0] = f[i][j][1] = inf;
f[0][0][0] = 0;
if (x % 10) f[0][1][1] = 10 - x % 10;
for (int i = 1; i <= 18; i++) {
int cur = x / p[i] % 10;
for (int j = 0; j <= k; j++) {
chkmn(f[i][j][0], f[i - 1][j][0]);
if (cur < 9) chkmn(f[i][j][0], f[i - 1][j][1]);
if (j) {
if (cur) chkmn(f[i][j][1], f[i - 1][j - 1][0] + (10 - cur) * p[i]);
chkmn(f[i][j][1], f[i - 1][j - 1][1] + (9 - cur) * p[i]);
}
}
}
cout << f[18][k][0];
for (int i = 1; i <= cnt; i++) cout << "0";
cout << "\n";
}
bool Med;
int main() {
// fprintf(stderr, "%.9lf\n", 1.0 * (&Mbe - &Med) / 1048576.0);
ios :: sync_with_stdio(false);
cin.tie(0), cout.tie(0);
init();
int t; cin >> t;
while (t--) mian();
// cerr << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
return 0;
}
G. Rectangle
给定 \(n\) 个矩形，选三条 \([0,10^9]\) 内的直线或竖线使得每个矩形至少和一条线有交。
求方案数对 \(998244353\) 取模后的结果。
\(1 \le n \le 10^5\)。
很炫酷的题。
根据直线的情况分类，有三条横线，一横两竖，以及对称情况。
对于三条横线，只和所有区间的 \(y\) 坐标相关，所以是⼀个一维问题。考虑枚举中间线的位置，上面和下面的线是上面未被覆盖和下面未被覆盖的区间的交。
对于一横两竖，考虑对横线做扫描线，变成了你要支持删除一个区间，插入一个区间，问用两个点覆盖剩下区间的方案数。假设所有区间为 \([l_i, r_i]\)。⾸先左边的点 \(L ≤ \min r_i\), 右边的点 \(R ≥ \max l_i\)。
维护 \(f(L)\) 表示左边的点在 \(L\) 位置，右边的点 \(R\) 的上界。每次插入一条线段 \([l, r]\)，会有如果 \(L < l\)，那么 \(R\) 一定要 \(≤r\)。也就是对于一个前缀，有一个 \(≤ r\) 的限制。于是每个位置的限制是后缀最小值。可以用楼房重建线段树维护，也可以线段树分治把删除扔掉，这样就可以直接线段树二分加区间赋值维护。
细节很多，总时间复杂度 \(\mathcal{O}(n \log^2 n)\)。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair <LL, LL> pi;
#define fi first
#define se second
constexpr int N = 2e5 + 5, T = 1e9, mod = 998244353, inv6 = 166374059;
constexpr LL inf = 1e18;
bool Mbe;
#define x1 elma1
#define y1 elma2
#define x2 elma3
#define y2 elma4
#define m ((l + r) >> 1)
#define lc x << 1
#define rc x << 1 | 1
void chkmx(int &x, int y) { x = x > y ? x : y; }
void chkmn(int &x, int y) { x = x < y ? x : y; }
void add(int &x, LL y) {
x = x + y >= mod ? x + y - mod : x + y;
}
int n, x1[N], y1[N], x2[N], y2[N], yy[N], ans, lp[N], rp[N];
int cx, cy, tx[N], ty[N];
int len[N << 2], mx[N << 2], tag[N << 2], sum[N << 2], lmax[N], rmin[N];
void build(int x, int l, int r) {
sum[x] = mx[x] = tag[x] = 0, len[x] = ty[r + 1] - ty[l];
if (l == r) return;
build(lc, l, m), build(rc, m + 1, r);
}
vector <pi> g1;
vector <pi> g2;
vector <pi> g3;
void push_tag(int x, int v) {
g1.emplace_back(x, mx[x]);
g2.emplace_back(x, tag[x]);
g3.emplace_back(x, sum[x]);
mx[x] = tag[x] = v;
sum[x] = 1LL * len[x] * v % mod;
}
void push_down(int x) {
if (tag[x]) {
g2.emplace_back(x, tag[x]);
push_tag(lc, tag[x]);
push_tag(rc, tag[x]);
tag[x] = 0;
}
}
void push_up(int x) {
g1.emplace_back(x, mx[x]);
g3.emplace_back(x, sum[x]);
mx[x] = mx[rc];
sum[x] = (sum[lc] + sum[rc]) % mod;
}
void cov(int x, int l, int r, int ql, int qr, int v) {
if (ql <= l && qr >= r) return push_tag(x, v);
push_down(x);
if (ql <= m) cov(lc, l, m, ql, qr, v);
if (qr > m) cov(rc, m + 1, r, ql, qr, v);
push_up(x);
}
int qry(int x, int l, int r, int ql, int qr) {
if (ql <= l && qr >= r) return sum[x];
push_down(x);
int res = 0;
if (ql <= m) add(res, qry(lc, l, m, ql, qr));
if (qr > m) add(res, qry(rc, m + 1, r, ql, qr));
return res;
}
int findpos(int x, int l, int r, int v) {
if (l == r) return l;
push_down(x);
if (mx[lc] > v) return findpos(lc, l, m, v);
return findpos(rc, m + 1, r, v);
}
vector <int> buc[N << 2];
void upd(int x, int l, int r, int ql, int qr, int id) {
if (ql <= l && qr >= r) return buc[x].emplace_back(id), void();
if (ql <= m) upd(lc, l, m, ql, qr, id);
if (qr > m) upd(rc, m + 1, r, ql, qr, id);
}
void solve(int x, int l, int r) {
int t1 = g1.size(), t2 = g2.size(), t3 = g3.size();
for (auto id : buc[x]) {
int nr = mx[1] <= y1[id] ? cy : findpos(1, 1, cy, y1[id]) - 1;
if (yy[id] <= nr) cov(1, 1, cy, yy[id], nr, y1[id]);
}
if (l == r) {
if (lmax[l]) {
int L = lower_bound(ty + 1, ty + cy + 1, lmax[l]) - ty;
if (L <= cy) {
int R = mx[1] <= rmin[l] ? cy : findpos(1, 1, cy, rmin[l]) - 1;
if (L <= R) {
int val = qry(1, 1, cy, L, R);
add(ans, 1LL * (1LL * (ty[R + 1] - ty[L]) * (rmin[l] + 1) % mod - val + mod) % mod * (tx[l + 1] - tx[l]) % mod);
}
}
}
} else solve(lc, l, m), solve(rc, m + 1, r);
while (g1.size() > t1) {
auto [x, y] = g1.back();
mx[x] = y;
g1.pop_back();
}
while (g2.size() > t2) {
auto [x, y] = g2.back();
tag[x] = y;
g2.pop_back();
}
while (g3.size() > t3) {
auto [x, y] = g3.back();
sum[x] = y;
g3.pop_back();
}
}
struct P1 {
priority_queue <int> q1, q2;
void insert(int x) {
q1.push(x);
}
void erase(int x) {
q2.push(x);
}
unsigned size() {
return q1.size() - q2.size();
}
bool empty() {
return q1.size() == q2.size();
}
int top() {
while (q2.size() && q2.top() == q1.top()) q1.pop(), q2.pop();
return q1.top();
}
void pop() {
while (q2.size() && q2.top() == q1.top()) q1.pop(), q2.pop();
q1.pop();
}
};
struct P2 {
priority_queue <int, vector <int>, greater <int>> q1, q2;
void insert(int x) {
q1.push(x);
}
void erase(int x) {
q2.push(x);
}
unsigned size() {
return q1.size() - q2.size();
}
bool empty() {
return q1.size() == q2.size();
}
int top() {
while (q2.size() && q2.top() == q1.top()) q1.pop(), q2.pop();
return q1.top();
}
void pop() {
while (q2.size() && q2.top() == q1.top()) q1.pop(), q2.pop();
q1.pop();
}
};
vector <int> ad[N];
int t1[N];
bool t2[N];
void solve() {
for (int i = 1; i <= 2 * n + 5; i++) {
ad[i].clear();
}
for (int i = 1; i <= 8 * n + 10; i++) {
buc[i].clear();
}
cx = cy = 0;
tx[++cx] = 1;
ty[++cy] = 1;
for (int i = 1; i <= n; i++) {
tx[++cx] = x1[i];
if (x2[i] != T) tx[++cx] = x2[i] + 1;
ty[++cy] = y1[i];
if (y2[i] != T) ty[++cy] = y2[i] + 1;
}
for (int i = 1; i <= cx; i++) lp[i] = 0, rp[i] = T + 1;
sort(tx + 1, tx + cx + 1);
sort(ty + 1, ty + cy + 1);
cx = unique(tx + 1, tx + cx + 1) - tx - 1;
cy = unique(ty + 1, ty + cy + 1) - ty - 1;
tx[cx + 1] = T + 1;
ty[cy + 1] = T + 1;
build(1, 1, cy);
for (int i = 1; i <= n; i++) {
int x1 = lower_bound(tx + 1, tx + cx + 1, ::x1[i]) - tx;
int x2 = lower_bound(tx + 1, tx + cx + 1, ::x2[i] + 1) - tx;
chkmx(lp[x2], ::x1[i]);
chkmn(rp[x1 - 1], ::x2[i]);
yy[i] = lower_bound(ty + 1, ty + cy + 1, y2[i] + 1) - ty;
if (x1 > 1) upd(1, 1, cx, 1, x1 - 1, i), ad[1].emplace_back(i), ad[x1].emplace_back(-i);
if (x2 <= cx) upd(1, 1, cx, x2, cx, i), ad[x2].emplace_back(i);
}
P1 nl;
P2 nr;
int L = 1, R = T;
for (int i = 1; i <= cx; i++) {
for (auto j : ad[i]) {
if (j > 0) {
nl.insert(y1[j]);
nr.insert(y2[j]);
} else {
j *= -1;
nl.erase(y1[j]);
nr.erase(y2[j]);
}
}
if (nl.empty()) lmax[i] = 0, add(ans, 1LL * T * (T - 1) / 2 % mod * (tx[i + 1] - tx[i]) % mod);
else {
lmax[i] = nl.top(), rmin[i] = nr.top();
if (lmax[i] <= rmin[i]) {
LL len = rmin[i] - lmax[i] + 1;
add(ans, 1LL * (1LL * T * (T - 1) / 2 - 1LL * (T - len) * (T - len - 1) / 2) % mod * (tx[i + 1] - tx[i]) % mod);
swap(lmax[i], rmin[i]);
lmax[i]++;
rmin[i]--;
}
}
if (lp[i]) {
chkmx(L, lp[i]);
chkmn(R, tx[i] - 1);
}
t1[i] = max(0, min(R, tx[i] - 1) - L + 1);
t2[i] = R >= tx[i];
}
L = 1, R = T;
for (int i = cx; i >= 1; i--) {
if (rp[i] <= T) {
chkmx(L, tx[i + 1]);
chkmn(R, rp[i]);
}
int k1 = max(0, R - max(L, tx[i + 1]) + 1);
bool k2 = L <= tx[i];
int len = tx[i + 1] - tx[i];
add(ans, 1LL * len * t1[i] % mod * k1 % mod);
if (t2[i]) add(ans, 1LL * len * (len - 1) / 2 % mod * k1 % mod);
if (k2) add(ans, 1LL * len * (len - 1) / 2 % mod * t1[i] % mod);
if (t2[i] && k2) add(ans, 1LL * len * (len - 1) % mod * (len - 2) % mod * inv6 % mod);
}
solve(1, 1, cx);
}
void mian() {
ans = 0;
cin >> n;
for (int i = 1; i <= n; i++) cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
solve();
for (int i = 1; i <= n; i++) swap(x1[i], y1[i]), swap(x2[i], y2[i]);
solve();
cout << ans << "\n";
}
bool Med;
int main() {
// fprintf(stderr, "%.9lf\n", 1.0 * (&Mbe - &Med) / 1048576.0);
ios :: sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t = 1; cin >> t;
while (t--) mian();
// cerr << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
return 0;
}
K. Magic
你有一个序列 \(a_0,a_1,a_2\dots a_{2n}\)，初始全为 \(0\)。
给定 \(n\) 个区间赋值操作，第 \(i\) 个操作 \((l_i,r_i)(1\le l_i,r_i\le 2n)\) 表示把区间 \([l_i,r_i)\) 全部赋值为 \(i\)，保证所有 \(l_i,r_i\) 互不相同。
你可以指定一个执行操作的顺序，最大化 \(\sum_{i=0}^{2n-1}[a_i\ne a_{i+1}]\)，输出这个最大值。
\(1\le n\le 5\times 10^3\)，空间限制 \(\text{16.0Mb}\)。
很炫酷的题。
先做一点基本转化：令 \(b_i = [a_i \neq a_{i-1}]\)，则操作 \([l_i,r_i]\) 即令 \(b_{l_i} = b_{r_i} = 1\)，\(b_j = 0(l_i + 1 \le j \le r_i-1)\)。
换⼀种方式考虑：要选择若干个位置，使得这些位置最后贡献给答案，要求合法且选择的位置数量最多。对于区间 \([l_i, r_i]\) 和 \([l_j, r_j]\)，若 \(l_i < l_j < r_i < r_j\)，那么如果选择 \(l_j\)，就意味着 \([l_i, r_i]\) 要在 \([l_j, r_j]\) 之前执行；同理如果选择 \(r_i\)，就意味着 \([l_j, r_j]\) 要在 \([l_i, r_i]\) 之前执行。
所以 \(r_i\) 与 \(l_j\) 不能同时选择，所以⼀定是⼀个建无向图后的独立集。下面证明这是充分的：
证明：
只要选择独立集后不会成环，那么就能够说明合法性。
如果成环，假设环上选了一个区间 \([l, r]\) 的右端点 \(r\)，导致它比某个区间 \([l’,r’](l < l’ < r < r’)\) 要晚执行。由于 \(l’\) 不能被选择，那么下一个环上的点一定是由于选择了 \(r’\) 导致的。那么以此类推，在这条链上的区间 \(r\) 一定单调递增，所以不可能成环。因此该限制充分。
于是问题转为二分图最大独立集问题。使用 bitset 优化匈牙利求出最大匹配即可，时间复杂度 \(\mathcal{O}(\frac{n^3}{\omega})\)。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair <LL, LL> pi;
#define fi first
#define se second
constexpr int N = 1e4 + 5, M = 20;
bool Mbe;
int n, m, ans;
int q[N], hd, tl;
int l[N], r[N], col[N], mat[N], prex[N], prey[N];
bitset <N> rest, nxt, e[N];
bool bfs(int s, int n) {
int pos = 0;
q[hd = tl = 1] = s;
rest.set();
while (hd <= tl && !pos) {
int u = q[hd++];
nxt = rest;
nxt &= e[u];
for (int i = nxt._Find_first(); i <= n; i = nxt._Find_next(i)) {
if (!mat[i]) {
mat[i] = u;
pos = u;
break;
}
rest[i] = false;
prex[mat[i]] = u;
prey[mat[i]] = i;
q[++tl] = mat[i];
}
}
if (!pos) return false;
for (int i = pos; i != s; i = prex[i]) {
mat[prey[i]] = prex[i];
}
return true;
}
void solve() {
cin >> n;
m = ans = n * 2;
for (int i = 1; i <= n; i++) {
cin >> l[i] >> r[i];
col[l[i]] = 0;
col[r[i]] = 1;
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
if (l[i] < l[j] && l[j] < r[i] && r[i] < r[j])
e[l[j]][r[i]] = 1;
}
for (int i = 1; i <= m; i++)
if (col[i] == 0 && bfs(i, m)) ans--;
cout << ans << "\n";
}
bool Med;
int main() {
// fprintf(stderr, "%.9lf\n", 1.0 * (&Mbe - &Med) / 1048576.0);
// freopen("ex_data3.in", "r", stdin);
// freopen("ex_data3.ans", "w", stdout);
ios :: sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t = 1;
while (t--) solve();
// cerr << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
return 0;
}