P9528 [JOIST 2022] 蚂蚁与方糖 / Ants and Sugar

这是一个二分图匹配的形式，转成最小割之后要求不存在两个异色点距离 \(\le L\) 且都没割掉。

考虑未被割掉点，贡献形如的是选若干点，异色点距离 \(>L\)。这个可以转化成确定黑点区间 \([l_i,r_i]\) 后，禁用 \([l_i-L,r_i+L]\) 的白点，然后前缀和优化成和 \(l,r\) 相关，形如 \((a_r-b_{r+L})+(b_{l-L}-a_l)\) 的形式，事实上这个可以直接线段树维护。

记前者为 \(A_r\)，后者为 \(B_l\)。具体地，类似动态 dp，记录 \(f_{0/1,0/1}\) 表示左右的状态。对于 \(a\) 的修改是容易的，因为我们只关心 \(A,B\) 选的 \(a\) 系数和，这个只和两个 01 mask 有关。

而对于 \(b\) 的修改相对困难一些。因为这个可以拆成区间 \(A,B\) 加和一个区间的 \(B\) 加，前者同上，但是后者我们需要知道划分的连续段数。

观察到后者修改区间长度其实是 \(\le 2L\) 的，这意味着最优解只有一个区间，那么连续段数就容易算了。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;const ll inf = 1e18;
const int kN = 5e5 + 5, kC = kN * 3, kS = kC * 4;
int n, t;
ll L;
struct Opr {int op, x, y;
} opr[kN];
int pos[kC];int P(int x) {return lower_bound(pos + 1, pos + t + 1, x) - pos - 1;
}struct M {ll a[2][2];M(ll _v = -inf) {a[0][0] = a[0][1] = a[1][0] = a[1][1] = _v;}M(ll w, ll x, ll y, ll z) {a[0][0] = w;a[0][1] = x;a[1][0] = y;a[1][1] = z;}
};
M operator * (const M &x, const M &y) {M res (-inf);for(int i : {0, 1}) {for(int j : {0, 1}) {res.a[i][j] = max({x.a[i][0] + y.a[0][j], x.a[i][1] + y.a[1][j], x.a[i][j], y.a[i][j]});}}return res;
}
M& operator += (M &x, const M &y) {for(int i : {0, 1}) {for(int j : {0, 1}) {x.a[i][j] += y.a[i][j];}}return x;
}
bool operator == (const M &x, const M &y) {for(int i : {0, 1}) {for(int j : {0, 1}) {if(x.a[i][j] != y.a[i][j]) return 0;}}return 1;
}#define ls (o << 1)
#define rs (o << 1 | 1)
struct SGT {M info[kS], tag[kS];SGT() {fill_n(info, kS, M (-inf));fill_n(tag, kS, M (0));}void Up(int o) { info[o] = info[ls] * info[rs]; }void Build(int o, int l, int r) {if(l == r) {info[o].a[0][1] = info[o].a[1][0] = 0;return ;}int mid = (l + r) >> 1;Build(ls, l, mid);Build(rs, mid + 1, r);Up(o);}void Adt(int o, const M &t) { info[o] += t, tag[o] += t; }void Dn(int o) {if(tag[o] == M(0)) return ;Adt(ls, tag[o]);Adt(rs, tag[o]);tag[o] = M(0);}void Update(int o, int l, int r, int x, int y, const M &v) {if((l > y) || (r < x)) return ;if((l >= x) && (r <= y)) return Adt(o, v);Dn(o);int mid = (l + r) >> 1;Update(ls, l, mid, x, y, v);Update(rs, mid + 1, r, x, y, v);Up(o);}
} sgt;int main() {// freopen("1.in", "r", stdin);// freopen("1.out", "w", stdout);ios::sync_with_stdio(0), cin.tie(0);cin >> n >> L;pos[++t] = -1 - L;for(int i = 1; i <= n; i++) {cin >> opr[i].op >> opr[i].x >> opr[i].y;pos[++t] = opr[i].x;pos[++t] = opr[i].x - L;pos[++t] = opr[i].x + L;}sort(pos + 1, pos + t + 1);t = unique(pos + 1, pos + t + 1) - pos - 1;ll suma = 0;sgt.Build(1, 1, t);for(int i = 1; i <= n; i++) {int x = opr[i].x, y = opr[i].y;if(opr[i].op == 1) {sgt.Update(1, 1, t, P(x), t, M(0, -y, y, 0));suma += y;}else {int p = P(x - L), q = P(x + L);sgt.Update(1, 1, t, q, t, M(0, y, -y, 0));sgt.Update(1, 1, t, p, q - 1, M(-y, 0, -y, -y));}cout << suma - max(0ll, sgt.info[1].a[0][0]) << "\n";}return 0;
}