UOJ Logo Universal Online Judge

UOJ

#730. 【JOISC2022】蚂蚁与方糖

附件下载 统计

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 君并不会真的拍手。因此蚂蚁的位置不会改变,方糖也不会被吃掉。

输入格式

第一行,两个正整数 $Q,L$,表示操作个数和蚂蚁可能吃到的方糖的范围。

接下来 $Q$ 行,其中第 $i$ $(1 \le i \le Q)$ 包含三个整数 $T_i,X_i,A_i$,表示一次操作。

输出格式

输出 $Q$ 行,第 $k$ $(1 \le k \le Q)$ 行包含一个整数,表示若 JOI 君在第 $k$ 次操作后拍了一次手,被至少一个蚂蚁吃掉的方糖的个数可能的最大值。

样例一

input

4 1
1 1 1
2 2 1
1 3 1
2 0 1

output

0
1
1
2

explanation

在这组样例中,所有操作和每个 $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$ 的限制。

样例二

见附件下载中的 ex_sugar2.inex_sugar2.ans

这组样例满足子任务 $1,2,4$ 的限制。

样例三

见附件下载中的 ex_sugar3.inex_sugar3.ans

这组样例满足子任务 $1,4$ 的限制。

样例四

见附件下载中的 ex_sugar4.inex_sugar4.ans

这组样例满足子任务 $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$

时间限制:$\texttt{4s}$

空间限制:$\texttt{1GB}$