神题。
考虑如何计算二分图最大匹配。考虑利用扩展 Hall 定理，即 \(|A| - \max\limits_{S \subseteq A} \{|S| - |N(S)|\}\)。回到原题就是 \(\text{sumred} - \max\limits_{\{[l_i, r_i]\} \text{两两不交}} \sum\limits_{i = 1}^k \text{sumred}(l_i, r_i) - \text{sumblue}(l_i - L, r_i + L)\)。
注意到 \(\{[l_i, r_i]\}\) 之间距离一定 \(> 2L\)，否则合并一定更优。
考虑用前缀和简化式子。设 \(R_i, B_i\) 分别为红 / 蓝点个数前缀和，设 \(p_i = -R_{i - 1} + B_{i - L - 1}, q_i = R_i - B_{i + L}\)，等价于交替选 \(p, q\) 的最大权值和。
容易线段树上维护 \(f_{i, 0/1, 0/1}\) 表示开始选了 \(p / q\)，结尾选了 \(p / q\) 的最大权值和。
然后考虑修改：
-
添加红点，相当于 \(p\) 在 \([x + 1, +\infty)\) 减 \(y\)，\(q\) 在 \([x, \infty)\) 加 \(y\)。相当于 \(p, q\) 在 \([x + 1, \infty)\) 中 \(p\) 减 \(y\)，\(q\) 加 \(y\)。\(q\) 在 \([x, x]\) 加 \(y\)。前者只会影响 \(f_{i, 0, 0}, f_{i, 1, 1}\)。
-
添加蓝点，相当于 \(p\) 在 \([x + L + 1, \infty)\) 加 \(y\)，\(q\) 在 \([x - L, \infty)\) 加 \(y\)。对于共同加减的区间可以像上面一样搞。对于 \(q\) 在 \([x - L, x + L + 1)\) 的区间加，因为相邻两个 \(q\) 的距离一定大于 \(2L\)，所以这段区间最多只选了一个 \(q\)。对于 \(f_{i, 0/1, 1}\) 加上 \(y\) 即可。
时间复杂度 \(O(q \log q)\)。
code
// Problem: P9528 [JOISC 2022 Day3] 蚂蚁与方糖
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P9528
// Memory Limit: 1 MB
// Time Limit: 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 500100;
ll n, m, tot, lsh[maxn], f[maxn << 2][2][2], tag1[maxn << 2], tag2[maxn << 2];
struct node {
ll op, x, y;
} a[maxn];
inline void pushup(int x) {
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
f[x][i][j] = max(f[x << 1][i][j], f[x << 1 | 1][i][j]);
for (int k = 0; k < 2; ++k) {
f[x][i][j] = max(f[x][i][j], f[x << 1][i][k] + f[x << 1 | 1][k ^ 1][j]);
}
}
}
}
inline void pushtag1(int x, ll y) {
f[x][0][0] += y;
f[x][1][1] -= y;
tag1[x] += y;
}
inline void pushtag2(int x, ll y) {
f[x][0][1] += y;
f[x][1][1] += y;
tag2[x] += y;
}
inline void pushdown(int x) {
if (tag1[x]) {
pushtag1(x << 1, tag1[x]);
pushtag1(x << 1 | 1, tag1[x]);
tag1[x] = 0;
}
if (tag2[x]) {
pushtag2(x << 1, tag2[x]);
pushtag2(x << 1 | 1, tag2[x]);
tag2[x] = 0;
}
}
void update1(int rt, int l, int r, int ql, int qr, ll x) {
if (ql > qr) {
return;
}
if (ql <= l && r <= qr) {
pushtag1(rt, x);
return;
}
pushdown(rt);
int mid = (l + r) >> 1;
if (ql <= mid) {
update1(rt << 1, l, mid, ql, qr, x);
}
if (qr > mid) {
update1(rt << 1 | 1, mid + 1, r, ql, qr, x);
}
pushup(rt);
}
void update2(int rt, int l, int r, int ql, int qr, ll x) {
if (ql > qr) {
return;
}
if (ql <= l && r <= qr) {
pushtag2(rt, x);
return;
}
pushdown(rt);
int mid = (l + r) >> 1;
if (ql <= mid) {
update2(rt << 1, l, mid, ql, qr, x);
}
if (qr > mid) {
update2(rt << 1 | 1, mid + 1, r, ql, qr, x);
}
pushup(rt);
}
inline int ID(ll x) {
return lower_bound(lsh + 1, lsh + tot + 1, x) - lsh;
}
void solve() {
scanf("%lld%lld", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%lld%lld%lld", &a[i].op, &a[i].x, &a[i].y);
lsh[++tot] = a[i].x;
}
sort(lsh + 1, lsh + tot + 1);
tot = unique(lsh + 1, lsh + tot + 1) - lsh - 1;
ll s = 0;
for (int i = 1; i <= n; ++i) {
ll op = a[i].op, x = a[i].x, y = a[i].y;
if (op == 1) {
s += y;
update1(1, 0, tot, ID(x + 1), tot, -y);
update2(1, 0, tot, ID(x), ID(x), y);
} else {
update1(1, 0, tot, ID(x + m + 1), tot, y);
update2(1, 0, tot, ID(x - m), ID(x + m + 1) - 1, -y);
}
printf("%lld\n", s - f[1][0][1]);
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}