#P18709. Moniphant Sleep

    ID: 18045 传统题 3000ms 1024MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2700省选/NOI-懒标记线段树标记复合不变量分析

Moniphant Sleep

Moniphant Sleep

你好,这里是 Moniphant!他有一个问题想请你解决。

Moniphant(原PDF插图)

Moniphant 发现自己可以进入不同深度的睡眠,在每一层都会遇到一个 Mofunfun。形式化地,有以下四种操作:

  1. 睡觉:进入下一层睡眠,即深度增加 1。
  2. 醒来:从当前层回到上一层,即深度减少 1。
  3. 对 Mofunfun 说“你是猪!”:激怒当前层的 Mofunfun,使它生气。
  4. Mofunfun 的报复:每一层的 Mofunfun 都尝试报复,只有生气的 Mofunfun 能够成功。成功的报复会使 Moniphant 回到所有生气的 Mofunfun 中层数最小、也就是最浅的那一层。报复之后,Mofunfun 不再生气。如果没有 Mofunfun 生气,则忽略这次操作。

下图的四幅原图依次对应上述四种操作。

四种操作(原PDF插图)

注意:当 Moniphant 回到更浅的层时,被离开的更深层中的 Mofunfun 会消失。

现在有 nn 个 Moniphant,编号为 1,…,n1,\ldots,n。你需要对编号属于区间 [l,r][l,r] 的所有 Moniphant 执行上述某种操作,或者询问某个 Moniphant 当前所在的睡眠深度。

在问题开始前,每个 Moniphant 都已执行了 5×1055\times10^5 次“睡觉”(第 1 种操作),即初始深度为 500000500000,且没有 Mofunfun 生气。

输入格式

第一行包含两个整数 n,qn,q(1≤n,q≤5×1051\le n,q\le5\times10^5),分别表示 Moniphant 的数量和操作数。

接下来 qq 行,每行包含三个整数 op,l,rop,l,r(op∈{1,2,3,4,5}op\in\{1,2,3,4,5\},1≤l≤r≤n1\le l\le r\le n)。

  • 如果 op≤4op\le4,对编号在 [l,r][l,r] 中的所有 Moniphant 执行第 opop 种操作。
  • 如果 op=5op=5,保证 l=rl=r,你需要输出编号为 ll 的 Moniphant 的睡眠深度。

输出格式

对每个第 5 种操作,输出一行一个整数,表示所询问的睡眠深度。

样例 1 输入

1 9
1 1 1
1 1 1
1 1 1
3 1 1
2 1 1
1 1 1
1 1 1
4 1 1
5 1 1

样例 1 输出

500004

样例 2 输入

3 7
2 1 3
3 1 3
1 1 3
1 1 3
5 1 1
4 1 3
5 1 1

样例 2 输出

500001
499999