http://arc076.contest.atcoder.jp/tasks/arc076_d
flowのお勉強。
Hallの結婚定理より、人の集合Xの誰かが座れる椅子の集合をP(X)と置けば必要な椅子の数はX-P(X)である。椅子の集合は[0,L]or[R,M+1]と表せるのでそこに含まれる最大の人の数を求めればよい。これは区間に値を加算し、最大値を出すsegtreeで高速に行うことが出来る。
struct node { ll sum, lazy; node() : sum(0), lazy(0){} node(ll sum, ll lazy) : sum(sum), lazy(lazy){} }; int M; node seg[200000 * 4]; inline void lazy_eval(int k, int l, int r) { if(seg[k].lazy) { seg[k * 2 + 1].sum += seg[k].lazy;//if range_min, erase (m - l) seg[k * 2 + 1].lazy += seg[k].lazy; seg[k * 2 + 2].sum += seg[k].lazy;//here too seg[k * 2 + 2].lazy += seg[k].lazy; seg[k].lazy = 0; } } void update(int a, int b, ll s, int k = 0, int l = 0, int r = M + 1) { if(b <= l || r <= a) return; if(a <= l && r <= b) { seg[k].sum += s;//here too seg[k].lazy += s; } else { int m = (l + r) / 2; lazy_eval(k, l, r); update(a, b, s, k * 2 + 1, l, m); update(a, b, s, k * 2 + 2, m, r); MAX(seg[k].sum, seg[k * 2 + 1].sum); MAX(seg[k].sum, seg[k * 2 + 2].sum); } } ll get_sum(int a, int b, int k = 0, int l = 0, int r = M + 1) { if(b <= l || r <= a) return 0; if(a <= l && r <= b) return seg[k].sum; else { int m = (l + r) / 2; lazy_eval(k, l, r); ll lsum = get_sum(a, b, k * 2 + 1, l, m); ll rsum = get_sum(a, b, k * 2 + 2, m, r); return max(lsum, rsum); } } int N; vector<int> P[MAX_N]; void solve() { cin >> N >> M; rep(i, 0, N) { int a, b; cin >> a >> b; P[a].push_back(b); } M++; rep(i, 0, M + 1) update(i, i + 1, i); ll res = max(N - M + 1, 0); rep(i, 0, M) { rep(j, 0, (int)P[i].size()) { int n = P[i][j]; update(0, n + 1, 1); } ll t = get_sum(i + 2, M + 1); MAX(res, t - M - i); } cout << res << "\n"; }
にぶたんしたら確かに区間の貪欲になるけど、勉強も兼ねて結婚定理から解いてみた。