P9528 [JOISC 2022] 蚂蚁与方糖 题解

Description

JOI 君是一个生物学家。他准备对蚂蚁和方糖做一些实验。

JOI 君的实验在一个长度为 $10^9$ 的木条上进行。这根木条被从左往右放置。木条上距离左端点 $x$ 的点被称作坐标为 $x$ 的点。

现在，木条上什么都没有。JOI 君将会进行 $Q$ 次操作。第 $i$ 个操作 $(1 \le i \le Q)$ 由三个整数 $T_i,X_i,A_i$ 描述，表示：

• 若 $T_i=1$，JOI 君在坐标为 $X_i$ 的点处放了 $A_i$ 个蚂蚁。
• 若 $T_i=2$，JOI 君在坐标为 $X_i$ 的点处放了 $A_i$ 块方糖。

由于蚂蚁和方糖都很小，所以可能会有一些蚂蚁和方糖放在同一个点上。JOI 君也可能在同一个点执行多次操作。

这次实验中使用的蚂蚁具有「好奇心强」的萌点。具体地，当 JOI 君拍手时，每个蚂蚁会执行以下操作：

• 如果存在一块方糖与该蚂蚁距离不超过 $L$，它会选择任意一块并吃掉。

可能存在多个蚂蚁同时吃掉一块方糖的情况。

对于每个 $k$ $(1\le k \le Q)$，JOI 君想要知道以下问题的答案。

• 假设 JOI 君在第 $k$ 次操作后拍了一次手，最多有多少块方糖被至少一个蚂蚁吃掉了？

请写一个程序，对于给定的 JOI 君执行的操作和 $L$ 的值，对于所有 $k$ 回答 JOI 君的每个问题。

注意 JOI 君并不会真的拍手。因此蚂蚁的位置不会改变，方糖也不会被吃掉。

对于所有数据，满足：

• $1 \le Q \le 500\,000$。
• $1 \le L \le 10^9$。
• $T_i \in \{1,2\}$。
• $0 \le X_i \le 10^9$ $(1 \le i \le Q)$。
• $1 \le A_i \le 10^9$ $(1 \le i \le Q)$。

Solution

首先可以转化为二分图最大匹配问题，即对于位置在 $x$ 的蚂蚁，向 $[x-L,x+R]$ 内的方糖连边，问最大匹配。

跑网络流显然是不行的。这时就要用到 Hall 定理：设左部点集合为 $A$，右部点集合为 $B$，则最大匹配为 $\displaystyle|A|-\max_{S\subseteq A}\{|S|-|\text{Nb}(S)|\}$。

注意到这里的每个左部点连接的是个长度相等的区间，所以用 Hall 定理会很好做。

具体的，选择的左部点集合一定构成若干个区间 $[l_1,r_1],[l_2,r_2],\ldots,[l_k,r_k]$，对应的右部点集合为 $[l_1-L,r_1+L],[l_2-L,r_2+L],\ldots,[l_k-L,r_k+L]$。

容易发现如果存在 $[l_i,r_i]$ 和 $[l_j,r_j]$ 有交或者 $[l_i-L,r_i+L]$ 和 $[l_j-L,r_j+L]$ 有交，那么将其合并一定更优。

所以最终的区间一定满足 $l_i-r_{i-1}>2L$。

设 $p_i=\text{cntant}_{1,i}-\text{cntsugar}_{1,i+L},q_i=\text{cntant}_{1,i-1}-\text{cntsugar}_{1,i-1-L}$，则一个区间 $[l,r]$ 的贡献为 $p_r-q_l$。

---

现在问题转化为了选择 $k$ 个区间，要求最大化 $\sum_{i=1}^{k}{(p_{r_i}-q_{l_i})}$。单次询问可以 dp 做。

考虑用线段树维护上面的那个 dp，设 $f_{x,0/1,0/1}$ 表示 $x$ 对应的区间，选的第一个为 $l$ 还是 $r$，最后一个是 $l$ 还是 $r$。

如果在 $x$ 处加入 $c$ 个蚂蚁，那么变化为：$[x,+\infty]$ 的 $p_i$ 加 $c_i$，$[x+1,+\infty]$ 的 $q_i$ 加 $c_i$。转换一下，变为 $p_x$ 加 $c_i$，$[x+1,+\infty]$ 的 $p_i$ 和 $q_i$ 同时加 $c_i$。

前面的是单点修改，后面的 $4$ 种 dp 最优选法一定不变，打个标记即可。

如果在 $x$ 处加入 $c$ 块方糖，变化为：$[x-L,x+L]$ 的 $p_i$ 加 $-c_i$，$[x+L+1,+\infty]$ 的 $p_i$ 和 $q_i$ 同时加 $-c_i$。

后面的和上面是一样的。由于最优方案一定满足 $r_i-l_{i-1}>2L$，所以 $[x-L,x+R]$ 内部的四种 dp 的最优方案选的点数也是确定的，同样打标记即可。

具体见代码。

时间复杂度：$O(Q\log Q)$。

Code

#include <bits/stdc++.h>

#define int int64_t

using pii = std::pair<int, int>;

const int kMaxN = 5e5 + 5;

int n, m, L;
int op[kMaxN], x[kMaxN], c[kMaxN], unq[kMaxN];

struct Node {
  int LL, LR, RL, RR;
  friend Node operator +(const Node &n1, const Node n2) {
    static Node ret;
    ret.LL = std::max({n1.LL, n2.LL, n1.LL + n2.RL, n1.LR + n2.LL});
    ret.LR = std::max({n1.LR, n2.LR, n1.LL + n2.RR, n1.LR + n2.LR});
    ret.RL = std::max({n1.RL, n2.RL, n1.RL + n2.RL, n1.RR + n2.LL});
    ret.RR = std::max({n1.RR, n2.RR, n1.RL + n2.RR, n1.RR + n2.LR});
    return ret;
  }
};

struct SGT {
  Node t[kMaxN * 4];
  std::array<int, 4> tag[kMaxN * 4];
  void pushup(int x) {
    t[x] = t[x << 1] + t[x << 1 | 1];
  }
  void addtag(int x, std::array<int, 4> v) {
    t[x].LL += v[0], t[x].LR += v[1], t[x].RL += v[2], t[x].RR += v[3];
    tag[x][0] += v[0], tag[x][1] += v[1], tag[x][2] += v[2], tag[x][3] += v[3];
  }
  void pushdown(int x) {
    if (tag[x][0] || tag[x][1] || tag[x][2] || tag[x][3]) {
      addtag(x << 1, tag[x]), addtag(x << 1 | 1, tag[x]);
      tag[x] = {0, 0, 0, 0};
    }
  }
  void update(int x, int l, int r, int ql, int qr, std::array<int, 4> v) {
    if (l > qr || r < ql) return;
    else if (l >= ql && r <= qr) return addtag(x, v);
    pushdown(x);
    int mid = (l + r) >> 1;
    update(x << 1, l, mid, ql, qr, v), update(x << 1 | 1, mid + 1, r, ql, qr, v);
    pushup(x);
  }
} sgt;

int getid(int x) { return std::lower_bound(unq + 1, unq + 1 + m, x) - unq; }

void discrete() {
  std::sort(unq + 1, unq + 1 + m);
  m = std::unique(unq + 1, unq + 1 + m) - (unq + 1);
}

void dickdreamer() {
  std::cin >> n >> L;
  for (int i = 1; i <= n; ++i) {
    std::cin >> op[i] >> x[i] >> c[i];
    unq[++m] = x[i];
  }
  discrete();
  int tot = 0;
  for (int i = 1; i <= n; ++i) {
    if (op[i] == 1) {
      int id = getid(x[i]);
      sgt.update(1, 1, m, id, id, {0, c[i], 0, c[i]});
      sgt.update(1, 1, m, id + 1, m, {-c[i], 0, 0, c[i]});
      tot += c[i];
    } else {
      int id1 = getid(x[i] - L), id2 = getid(x[i] + L + 1);
      sgt.update(1, 1, m, id1, id2 - 1, {0, -c[i], 0, -c[i]});
      sgt.update(1, 1, m, id2, m, {c[i], 0, 0, -c[i]});
    }
    std::cout << tot - std::max<int>(sgt.t[1].LR, 0) << '\n';
  }
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}