← 返回题目列表

AtCoder · abc441_g

G. 章鱼烧和翻转

中文机器翻译题面 查看原题

分数: 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