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$|