分数: 575 点
问题陈述
N 板从左到右呈直线排列。 让我们调用 i左起第一个车牌 (1\le i\le N) 板 i。 最初,所有盘子都面朝上放置,没有盘子上有章鱼烧(章鱼小丸子)。
进程总计 Q 以下三种类型的查询:
- 类型 1:给你整数 L,R,X。对于 i=L,L+1,\ldots,R,如果板 i 面朝上放置,放置 X 章鱼烧盘 i.
- 类型 2:给你整数 L,R。对于 i=L,L+1,\ldots,R,如果盘子上至少有一份章鱼烧 i,把盘子里的章鱼烧全部吃掉 i。翻转板 i (如果盘子面朝上放置,则面朝下放置;否则,面朝上放置)。
- 类型 3:给你整数 L,R。打印盘子中一盘章鱼烧的最大数量 L, L+1,\ldots, R.
约束
- 1\le N\le2\times10 ^ 5
- 1\le Q\le2\times10 ^ 5
- 在所有查询中, 1\le L\le R\le N.
- 输入类型 1 查询, 1\le X\le10 ^ 9.
- 至少有一种类型 3 查询。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N Q
\mathrm{query} _ 1
\mathrm{query} _ 2
\vdots
\mathrm{query} _ Q
在这里, \mathrm{query} _ i 代表 i-th (1\le i\le Q) 查询并以下列格式之一给出:
t L R X
t L R
这些表明 i-第一个查询的类型 t 和给定的整数是 L,R,X or L,R。 类型 1 查询以前一种格式给出,其他查询以后一种格式给出。
输出
让 q 是类型的数量 3 查询。打印 q 行。 的 i第行 (1\le i\le q) 应包含以下问题的答案 i第类型 3 从头开始查询。
示例输入 1
6 6 1 3 5 4 3 2 3 1 1 6 2 2 3 4 3 1 6 3 2 3
示例输出 1
4 6 2
每次查询时,每个盘子的状态以及上面章鱼烧的数量如下图所示。

第二次查询时,板块间 2 和 3,章鱼烧较多的是一盘 3。
因此,打印 4, 盘中章鱼烧的数量 3,在第一行。
第五次查询时,板块中 1, 2,\ldots, 6,章鱼烧最多的是盘子 5。
因此,打印 6, 盘中章鱼烧的数量 5,在第二行。
第六次查询时,板块中 2 和 3,章鱼烧较多的是一盘 2。
因此,打印 2, 盘中章鱼烧的数量 2,在第三行。
示例输入 2
2 8 1 1 2 1000000000 1 1 2 1000000000 2 2 2 1 1 2 1000000000 1 1 2 1000000000 1 1 2 1000000000 3 2 2 3 1 2
示例输出 2
0 5000000000
请注意,章鱼烧不能放置在面朝下放置的盘子上。
另外,请注意,答案可能是 2 ^ {32} 或更多。
示例输入 3
24 30 1 11 24 4326 1 4 16 1149 1 14 20 2331 1 12 14 8930 1 22 23 6989 3 15 20 3 10 19 1 3 12 7988 1 18 23 8450 3 9 19 3 13 15 2 8 15 2 9 14 1 11 17 4062 1 6 15 1721 3 7 13 1 11 20 8541 1 8 10 3748 1 1 17 3252 2 9 23 2 1 23 3 2 22 1 5 23 7468 3 1 12 3 12 19 2 6 24 3 2 14 3 1 15 2 15 19 3 2 14
示例输出 3
7806 16736 22393 16736 10858 0 7468 7468 0 0 0