问题抽象

我们有一个数轴，初始为空。进行 $Q$ 次操作，每次在位置 $X_i$ 增加 $A_i$ 只蚂蚁（$T_i=1$）或 $A_i$ 块方糖（$T_i=2$）。

每次操作后，我们要回答：如果此时拍手，每只蚂蚁可以吃掉距离不超过 $L$ 的任意一块方糖，那么最多有多少块方糖被至少一只蚂蚁吃掉。

这是一个典型的二分图最大匹配问题：

• 左部点：所有蚂蚁
• 右部点：所有方糖
• 边：当 $|x_a - x_s| \le L$ 时，蚂蚁 $a$ 与方糖 $s$ 之间有边

但直接建图不可行，因为 $Q$ 可达 $5\times 10^5$，蚂蚁和方糖数量可能很大。

---

关键观察

1. 区间匹配模型

由于距离限制 $L$，位置为 $x$ 的蚂蚁能吃到位置在 $[x-L, x+L]$ 范围内的方糖。

这可以转化为：将蚂蚁视为需求点，方糖视为供应点，求最大匹配。

2. Hall 定理的应用

根据 Hall 定理，二分图存在完美匹配的充要条件是：对于左部点的任意子集 $S$，其邻居节点数不少于 $|S|$。

在我们的问题中，最大匹配值 = 蚂蚁总数 - max{0, max over S( |S| - |N(S)| )}

但更实用的形式是：最大匹配 = 方糖总数 - max{0, max over T( |T| - |N(T)| )}，其中 $T$ 是方糖的子集。

3. 区间交的优化表达

考虑数轴上的一个区间 $I$，设：

• $ant(I)$ = 区间 $I$ 内的蚂蚁数量
• $sugar(I)$ = 区间 $I$ 内的方糖数量

对于任意区间 $I$，如果 $ant(I) > sugar(I)$，那么至少有 $ant(I) - sugar(I)$ 只蚂蚁无法匹配。

实际上，最大无法匹配的蚂蚁数 = $\max\limits_{\text{所有区间 } I} [ant(I) - sugar(I)]$

因此：被吃掉的方糖数 = 总蚂蚁数 - $\max(0, \max\limits_I [ant(I) - sugar(I)])$

---

算法核心

我们需要维护：

• 总蚂蚁数 $totalAnts$
• 对于所有区间 $I$，$ant(I) - sugar(I)$ 的最大值

但"所有区间"太多，需要进一步优化。

4. 关键区间缩减

实际上，只需要考虑形如 $[x, x+2L]$ 的区间，因为：

• 蚂蚁在 $p$ 能吃到方糖的范围是 $[p-L, p+L]$
• 如果考虑一个蚂蚁集合和它能吃到的方糖集合，相关的区间长度与 $L$ 有关

经过分析，最优的 $I$ 一定是某个方糖位置或蚂蚁位置附近的区间。具体来说，只需要考虑以下区间：

• 以某个蚂蚁位置为左端点，长度为 $2L$ 的区间
• 以某个方糖位置为右端点，长度为 $2L$ 的区间

5. 数据结构维护

我们需要支持：

• 单点修改（增加蚂蚁或方糖）
• 区间查询 $ant(I) - sugar(I)$ 的最大值

这可以用线段树维护。将坐标离散化后，对每个区间 $[l, r]$ 维护：

• 该区间内的蚂蚁总数
• 该区间内的方糖总数
• $ant - sugar$ 的最大值（以及前后缀最大值，用于合并）

每次操作后，我们计算：

$$\text{答案} = totalAnts - \max(0, \text{线段树查询的全局最大值}) $$

---

复杂度分析

• 坐标离散化：$O(Q\log Q)$
• 每次操作更新线段树：$O(\log Q)$
• 总复杂度：$O(Q\log Q)$

---

总结

这道题的解决关键在于：

1. 问题转化：将原问题转化为二分图最大匹配
2. Hall 定理应用：将匹配问题转化为区间数量差的最大值问题
3. 区间优化：发现只需要考虑特定长度的区间
4. 数据结构：用线段树维护区间数量差的最大值

这种"Hall定理 + 线段树维护极值"的思路在许多区间匹配问题中都非常有效，特别是当匹配条件与距离相关时。