ARC076 F – Exhausted?[题目大意]
\(有m个座位，分别位于坐标为1,2,3,…,m的地方；n个客人，第i位客人只坐位于[0,li]∪[ri,m]的座位。每个座位只能坐一个人，问最少需要添加几个座位才能使所有人坐下？\)
[Solution]
本题考察对霍尔定理的理解， $对于二分图G= , 设|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 #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#define fi first#define se second#define sz(a) a.size()#define all(v) v.begin(), v.end()#define int long longusing namespace std;const int maxn = 5e5 + 10, mod = 1e9 + 7;// mod = 1949777;const double EPS = 1e-3;int n, m;vector a[maxn];struct segment_tree{ int N; long long P; vector 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(4 * N - 1, 0); A = ST; M = vector(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 > 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 > 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 > 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 > 1); int res = -1e15; if (l <= mid) res = max(res, getmax(l, r, s, mid, 2 * p)); if (mid > 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 > 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;}