P9528 [JOISC 2022] 蚂蚁与方糖
题目背景
JOISC2022 D3T3
题目描述
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】**
在这组样例中,所有操作和每个 $k$ 的答案如下:
1. JOI 君在坐标为 $1$ 的点放了一个蚂蚁。
由于没有方糖,对应的答案为 $0$。
2. JOI 君在坐标为 $2$ 的点放了一块方糖。
假设 JOI 君此时拍手,则坐标为 $1$ 的蚂蚁会吃掉坐标为 $2$ 的方糖,所以对应的答案为 $1$。
3. JOI 君在坐标为 $3$ 的点放了一个蚂蚁。
假设 JOI 君此时拍手,则坐标为 $1,3$ 的蚂蚁会同时吃掉坐标为 $2$ 的方糖,所以对应的答案为 $1$。
4. JOI 君在坐标为 $0$ 的点放了一块方糖。
假设 JOI 君此时拍手,则坐标为 $1,3$ 的蚂蚁可以分别吃掉坐标为 $0,2$ 的方糖,所以对应的答案为 $2$。
这组样例满足子任务 $1,2,4$ 的限制。
**【样例解释 #2】**
这组样例满足子任务 $1,2,4$ 的限制。
**【样例解释 #3】**
这组样例满足子任务 $1,4$ 的限制。
**【样例解释 #4】**
这组样例满足子任务 $1,3,4$ 的限制。
**【数据范围】**
对于所有数据,满足:
- $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)$。
详细子任务附加限制及分值如下表所示:
|子任务编号|附加限制|分值|
|:-:|:-:|:-:|
|$1$|$Q \le 3\,000$|$6$|
|$2$|$L=1$,$X_i \le Q-1$,$X_i+T_i$ 是偶数 $(1\le i\le Q)$|$16$|
|$3$|$Q$ 是偶数,$T_i = 1$ $(1 \le i \le Q/2)$,$T_i = 2$ $(Q/2+1 \le i \le Q)$|$26$|
|$4$|无附加限制|$52$|