题目背景

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

输入格式

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

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

输出格式

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

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

0
1
1
2

20 1
2 16 778913911
1 7 558407445
1 1 589762439
1 17 74646747
1 1 149104909
1 15 956697952
2 6 389372991
2 4 867453845
1 15 157353445
1 9 846177695
1 7 747107163
2 10 525670462
2 16 478912944
2 6 301733761
2 12 132966485
1 1 748012313
2 10 830922632
1 19 969484637
1 13 370330582
1 1 464798040

0
0
0
74646747
74646747
778913911
1168286902
1168286902
1168286902
1168286902
1168286902
1693957364
2103741597
2405475358
2405475358
2405475358
2725982591
2725982591
2858949076
2858949076

20 6
2 27 12
2 9 11
1 36 10
2 39 4
2 14 9
2 33 7
2 38 20
2 0 20
2 25 16
1 14 3
1 13 19
2 6 4
2 15 6
2 33 4
1 12 11
1 44 1
2 17 14
2 12 19
1 48 18
2 30 16

0
0
0
4
4
10
10
10
10
13
30
30
32
32
40
41
44
44
44
44

20 268886972
1 984472666 733463744
1 478477245 94817772
1 242536956 330762563
1 65794782 319137646
1 320548477 937296140
1 815011370 938193848
1 565184190 917533785
1 245417414 534089975
1 529908772 977043962
1 603891865 700935654
2 167042244 479827216
2 173921297 798343455
2 916159596 810126726
2 999299355 465535307
2 965968070 501768990
2 936073643 174976034
2 832859952 778072072
2 955489596 704853861
2 246733786 382428992
2 227669861 390905006

0
0
0
0
0
0
0
0
0
0
479827216
1278170671
2088297397
2553832704
2949828263
2949828263
3727900335
3727900335
4110329327
4501234333

提示

【样例解释 #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$