33OJ
登录 注册

#P17627. 过期的命令

过期的命令

背景

已经过期的命令,没有必要遵守。

项链是我给她的。既然已经用不上了,我应该有权收回那条项链。

「我想问一下当作参考,我还给你之后会怎样?」
「我会把项链丢掉,跟你就此结束。」
「结束是什么意思?」

她像是现在才第一次听说般,问起这个理论上她应该知道的事情。

「我不会再跟你见面。」
「你要是和宇都宫念同一所大学,我们随时都能见面耶。即使如此也一样?」

「我们一开始就约好只到毕业典礼啊。就算随时都能见面,我也不会跟你见面。把项链还我啦。」
「还给你的话,你会丢掉吧?未免太浪费了。」

真不干脆。

她应该早就知道我今天会说些什么了,我们也约好只到毕业典礼为止。尽管事先没有连要将项链还给我这件事都讲定,但这并非需要抗拒的事情。把这种宛如项圈的东西给丢掉,对她来说也是好事才对。

「一点都不浪费。还给我。」

我像是在催促她似的伸出手。

「你这个人真的很小气耶。」

这样说完后,仙台同学夸张地叹了口气。

随即缓缓地解开项链。

「拿去。」

她将项链放在桌上。

我把手伸向银色的项链,然而在碰到之前,仙台同学开了口:「不过在那之前──」

「我有东西想给你看,所以你等一下。」

「有东西想让我看?」
「没错。」

仙台同学一边说:「就是这个。」一边从书包里抽出某个东西,放到项链旁边。

「……信?」

题目描述

建议阅读样例解释以更好地理解题意。

宫城眼前的信是一条长度为 nn 的纸条,被平铺在数轴上,覆盖了区间 [0,n][0, n]。

接下来她要对这张纸条进行 mm 次折叠操作,对于第 ii 次折叠,她会给定两个参数 pi,lip_i,l_i。

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

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

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

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

输入格式

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

接下来的 mm 行,每行两个数,第 ii 行的为 pip_i 和 lil_i,代表第 ii 次折叠操作,含义见题目描述。

输出格式

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

4 2
1 2
2 1
2
4

6 6
1 2
1 4
1 1
1 2
2 1
1 1

2
2
2
4
6
6

7 3
2 1
2 1
2 1

2
2
3

6 6
1 2
2 4
1 1
1 2
2 1
1 1

2
2
4
4
6
6

提示

样例解释:

对于第一组样例:

所有操作前,被覆盖的位置为 [0.5,1.5,2.5,3.5][0.5,1.5,2.5,3.5],层数均为 11。纸条覆盖数轴长度为 44。

第二次操作前,被覆盖的位置为 [2.5,3.5][2.5,3.5],层数均为 22。纸条覆盖数轴长度为 22。

所有操作结束时,被覆盖的位置为 [2.5][2.5],层数均为 44。纸条覆盖数轴长度为 11。


对于第二组样例前 44 个操作,每次操作前,纸条在数轴上的覆盖情况依次如下:

层数为 11,纸条覆盖数轴长度为 66。

层数为 22,纸条覆盖数轴长度为 44。

层数为 22,纸条覆盖数轴长度为 44。

层数为 22,纸条覆盖数轴长度为 33。


数据范围:

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

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

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

::cute-table{tuack} | 子任务编号 | n≤n\le | m≤m\le | 特殊性质 | 分值 | |:-:|:-:|:-:|:-:|:-:| | 00 | 1010 | 1010 | 无 | 55 | | 11 | 50005000 | 50005000 | ^ | ^ | | 22 | 2×1042 \times 10^4 | 10410^4 | ^ | ^ | | 33 | 5×1055 \times 10^5 | 10510^5 | AB | ^ | | 44 | ^ | ^ | A | ^ | | 55 | 5×1065 \times 10^6 | ^ | C | ^ | | 66 | ^ | 5×1055 \times 10^5 | 无 | 2020 |

特殊性质 A:∀1≤i≤m\forall 1 \le i \le m,有 li=1l_i=1。

特殊性质 B:∀1≤i≤m\forall 1 \le i \le m,有 pi=2p_i=2。

特殊性质 C:数据随机生成。具体的,对于所有的 1≤i≤m1 \le i \le m,pip_i 在 {1,2}\{1,2\} 中等概率选取,设当前纸条覆盖长度为 LL,lil_i 在 [0,L][0,L] 中的所有整数中等概率选取。