ARC076 F - Exhausted?
[題目大意]
\(有m個座位，分別位于坐標為1,2,3,...,m的地方；n個客人，第i位客人只坐位于[0,li]∪[ri,m]的座位，每個座位只能坐一個人，問最少需要添加幾個座位才能使所有人坐下？\)
[Solution]
本題考察對霍爾定理的理解， $對于二分圖G=<V_1, V_2, E> , 設|V_1| < |V_2| , 則G中存在V_1 到V_2的完美匹配當且僅當對于任意S\subset V_1, 對于S的鄰域N(S), 均有|S| \le |N(S)| $
而霍爾定理有一個推論， 就是若使G 中存在完美匹配， 則最少補充\(max\{0, |S| - |N(S)|\}\) 條邊
回到本題， 對于一個人， 把他看做左部點， 把座位1到m看做右部， 將客人向所有\(i\in[1, l_i] \cup [r_i, m]\)連邊
因為左部S所對應的右部節點的形式為\([1, l] \cup [r, m]\) 節點數為\(m - (r - l + 1）= m - r + l - 1\)
那么依據霍爾定理， 答案就是 \(|S| - m + r - l + 1\)
那么， 求出上述式子的最大值即可， 但是列舉S的復雜度太高， 于是考慮右部區間\([L, R]\) 找出對應的左部節點，所以可以將人\(l_i, r_i\) 按\(l_i\) 升序， 建一棵線段樹存盤\(r_i\) ，將右部節點映射上去， 并把初值設為i,，迭代\(l\) , 每次將左端點是\(l\)的\(r_i\), 更新入線段樹, 即將\([l, r]\) 區間加一， 每次求出\([L, m]\)的最大值，
對于\(r_i = m + 1\)的點， 在額外建一個點m + 1，存盤即可
#include <bits/stdc++.h>
#define for_(i,a,b) for (ll i = (a); i < (b); i++)
#define rep_(i,a,b) for (ll i = (a); i <= (b); i++)
#define ll long long
#define pii pair<int, int>
#define fi first
#define se second
#define sz(a) a.size()
#define all(v) v.begin(), v.end()
#define int long long
using namespace std;
const int maxn = 5e5 + 10, mod = 1e9 + 7;// mod = 1949777;
const double EPS = 1e-3;
int n, m;
vector<int> a[maxn];
struct segment_tree{
int N;
long long P;
vector<long long> ST, A, M, F; // A -> tag add / M -> tag mul /F -> tag max
segment_tree(int n) {
N = 1;
while(N < n) {
N *= 2;
}
ST = vector<long long>(4 * N - 1, 0);
A = ST;
M = vector<long long>(4 * N - 1, 1);
F = A;
P = 1e15;
}
void pushdown(int s, int t, int p) {
int l = 2 * p, r = 2 * p + 1, mid = s + ((t - s) >> 1);
if (M[p] != 1) {
M[l] *= M[p], M[l] %= P;
A[l] *= M[p], A[l] %= P;
ST[l] *= M[p], ST[l] %= P;
F[l] *= M[p], F[l] %= P;
M[r] *= M[p], M[r] %= P;
A[r] *= M[p], A[r] %= P;
ST[r] *= M[p], ST[r] %= P;
F[r] *= M[p], F[r] %= P;
M[p] = 1;
}
if (A[p] != 0) {
ST[l] += A[p] * (mid - s + 1), ST[l] %= P;
A[l] += A[p], A[l] %= P;
F[l] += A[p], F[l] %= P;
ST[r] += A[p] * (t - mid), ST[r] %= P;
A[r] += A[p], A[r] %= P;
F[r] += A[p], F[r] %= P;
A[p] = 0;
}
return;
}
void pushup(int p) {
int l = 2 * p, r = 2 * p + 1;
ST[p] = (ST[l] + ST[r]) % P;
F[p] = max(F[l], F[r]);
return;
}
void mul(int l, int r, int c, int s, int t, long long p) {
if (l <= s && t <= r) {
M[p] *= c, A[p] *= c, ST[p] *= c;
M[p] %= P, A[p] %= P, ST[p] %= P;
F[p] *= c, F[p] %= P;
return;
}
int mid = s + ((t - s) >> 1);
pushdown(s, t, p);
if (l <= mid) mul(l, r, c, s, mid, p * 2);
if (mid < r) mul(l, r, c, mid + 1, t, p * 2 + 1);
//(ST[p] = ST[p * 2] + ST[p * 2 + 1]) %= P;
pushup(p);
}
void add(int l, int r, int c, int s, int t, long long p) {
if (l <= s && t <= r) {
ST[p] += (t - s + 1) * c; ST[p] %= P;
A[p] += c; A[p] %= P;
F[p] += c, F[p] %= P;
return;
}
int mid = s + ((t - s) >> 1);
pushdown(s, t, p);
if (l <= mid) add(l, r, c, s, mid, 2 * p);
if (mid < r) add(l, r, c, mid + 1, t, 2 * p + 1);
//(ST[p] = ST[2 * p] + ST[2 * p + 1]) %= P;
pushup(p);
return;
}
long long getsum(int l, int r, int s, int t, int p) {
if (l <= s && t <= r) {
return ST[p];
}
int mid = s + ((t - s) >> 1);
pushdown(s, t, p);
long long res = 0;
if (l <= mid) res += getsum(l, r, s, mid, 2 * p), res %= P;
if (mid < r) res += getsum(l, r, mid + 1, t, 2 * p + 1), res %= P;
return res;
}
int getmax(int l, int r, int s, int t, int p) {
if (l <= s && t <= r) return F[p];
pushdown(s, t, p);
int mid = s + ((t - s) >> 1);
int res = -1e15;
if (l <= mid) res = max(res, getmax(l, r, s, mid, 2 * p));
if (mid < r) res = max(res, getmax(l, r, mid + 1, t, 2 * p + 1));
return res;
}
};
signed main() {
cin >> n >> m;
int ans = max(0LL, n - m);
m++; // 由于線段樹板子是Indexed_1，所以坐標整體+1
segment_tree T(m + 2);
for (int i = 1; i <= m + 1; i++) T.add(i, i, i - 1, 1, m + 1, 1);
for (int i = 1; i <= n; i++) {
int u, v; cin >> u >> v;
u++, v++;
a[u].push_back(v);
}
for (int i = 1; i <= m; i++) {
for (int j = 0; j < (int)a[i].size(); j++) {
T.add(1, a[i][j], 1, 1, m + 1, 1);
}
ans = max(ans, -(i - 1) - (m - 1) - 1 + T.getmax(i + 1, m + 1, 1, m + 1, 1)); //即上文的式子
}
cout << ans << endl;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/547074.html
標籤：其他
上一篇：三維模型輕量化方面存在主要問題