33OJ
登录 注册

#P17628. 信封的选择

信封的选择

背景

我把画有房子平面图的那张纸对折再对折,放在桌上。

「总之你选一边吧。」
「你说要选,是要选什么?」

其实我不用问也知道,却还是问了她。

「项链和信封,选你喜欢的那一边,我会遵照你的选择去做。如果你选了项链,我就不会再跟你见面,即使看到你也不会搭话。今天就是我们最后一次见面。」

「那我要是选信封呢?」

「你就要和我一起住。」

题目描述

仙台同学给了宫城 10910^9 张纸条,分别编号为 1,2,⋯ ,1091, 2, \cdots, 10^9。纸条的初始长度为 nn。

最初,所有的纸条都被平铺在数轴上,覆盖了区间 [0,n][0, n]。

宫城会对这些纸条进行 mm 次折叠操作。对于第 ii 次操作,她会给定三个参数 ti,pi,lit_i,p_i,l_i。

设当前最小的被纸条 tit_i 覆盖的点为 kk。

  • 若 pi=1p_i=1,以点 (k+li)(k+l_i) 的位置为折点,将纸条 tit_i 在数轴上小于 (k+li)(k+l_i) 的部分折向右边。

  • 若 pi=2p_i=2,以点 (k+li)(k+l_i) 的位置为折点,将纸条 tit_i 在数轴上大于 (k+li)(k+l_i) 的部分折向左边。

每次折叠操作后,宫城都想知道纸条 tit_i 的最大层数。形式化地,纸条层数是指在数轴上所有形如 (x+0.5)(x+0.5) 的点(xx 为整数)中,被该纸条覆盖的最大厚度。

输入格式

第一行,两个数,nn 和 mm,表示纸条长度和操作次数。

接下来的 mm 行,每行三个数,第 ii 行的为 ti,pit_i,p_i 和 lil_i,代表第 ii 次折叠操作。

输出格式

共 mm 行,每行一个数,其中第 ii 行的表示在第 ii 次操作后,数轴上的点最多被纸条 tit_i 覆盖了几层。

6 8
1 1 2
1 2 4
1 1 1
2 1 2
1 2 1
1 1 1
2 2 1
2 1 1
2
2
4
2
5
6
4
4
10 10
1 1 3
1 2 2
2 1 4
1 1 1
2 2 3
1 2 2
3 1 5
2 1 2
1 1 1
3 2 2
2
4
2
4
4
6
2
7
10
4

提示

数据范围:

本题目采用子任务捆绑测试。

对于所有数据:1≤n≤5×1051 \le n \le 5 \times 10^5,1≤m≤1.2×1051 \le m \le 1.2 \times 10^5。

  • ∀1≤i≤m\forall 1 \le i \le m,有 1≤ti≤1091 \le t_i \le 10^9,pi∈{1,2}p_i \in \{1,2\},li≥0l_i \ge 0,且 lil_i 小于等于操作时纸条 tit_i 覆盖数轴的长度。

::cute-table{tuack} | 子任务编号 | n≤n\le | m≤m\le | 特殊性质 | 分值 | |:-:|:-:|:-:|:-:|:-:| | 00 | 5×1055 \times 10^5 | 1.2×1051.2 \times 10^5 | ti≤400t_i \le 400 | 1010 | | 11 | 2×1052 \times 10^5 | 5×1045 \times 10^4 | 无 | 2020 | | 22 | 5×1055 \times 10^5 | 1.2×1051.2 \times 10^5 | ^ | ^ |


松开仙台同学的头发后,她便想转过头来,于是我按住她的头,让她面向前面,不能转过来。

「意思是你选择了信封?」
「你觉得选项链比较好的话,那我就选项链。」

我尽量用一如往常的语气说完后,她抓住我按在她头上的手。

「如果宫城要用四年当一个段落,得好好加油,别留级喽。」
「仙台同学真的老爱说些多余的话耶。」

总觉得这种时候应该还有其他更合适的发言才对。虽然我不知道那是什么,但是叫人家别留级这种话绝对不是现在该说的话。

「你这只手放开啦。我也会放手。」

她这么说着,用力握了一下我按在她头上的那只手,随即放开。无可奈何地照她说的放手后,她转过来面向我,接着理所当然地握住我的手。

「以后我可以叫你志绪理吗?」

「不可以。」

「宫城好小气。」
「仙台同学很啰唆耶。」

听到我的声音,仙台同学嘻嘻笑着。

她真的就会说些多余的话。

不过只有四年。

如果就这点时间,要我跟这样的她共度这段时光也行。

我回握住她就这样牵着我,没有放开的手。