← 返回题目列表

AtCoder · arc047_d

D. 姓名查询

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

問題文

垂直 N 线,水平 N 我有一列方格纸。

从这张方格纸上左上角的方块开始 X 向右方格 Y 单击您已前进的方块。 我们称之为 (X, Y) 。 换句话说,最左上角的正方形就是 (0, 0) ,右下方块是一个方块 (N-1, N-1) 。

最初,所有方块都包含整数。 0 已写入。

在这张方格纸上 考虑执行 Q 查询操作。查询操作是 3 有以下类型。 所有变成

  • 1 A B C : A ≦ X+Y ≦ B 的方块 (X, Y) 中写入的整数 添加 C 。0 ≦ A ≦ B ≦ 2N-2, -10^5 ≦ C ≦ 10^5 保证得到满足。
  • 2 A B C : A ≦ X-Y ≦ B 的方块 (X, Y) 中写入的整数 添加 C 。1-N ≦ A ≦ B ≦ N-1, -10^5 ≦ C ≦ 10^5 保证得到满足。
  • 3 A B C D : A ≦ X ≦ B 和 C ≦ Y ≦ D 的方块 (X,Y) 中的最大值 M 并在该范围内 找出写有 M 的方格数。0 ≦ A ≦ B ≦ N-1, 0 ≦ C ≦ D ≦ N-1 保证得到满足。

编写一个程序来顺序处理这样的查询。


入力

输入将以以下格式从标准输入给出。

N Q
Query_1
Query_2
:
Query_Q
  • 1 第一行是一个整数,表示方格纸的尺寸。 N(1 ≦ N ≦ 5,000) 和一个表示查询数量的整数 给出了第 Q(1 ≦ Q ≦ 5,000)用空格分隔。
  • 2 从线 Q 线内 给出了 i 在线 i 个查询。查询的格式如问题文本中所示。
  • 3 查询类型为 可以给出 1 或更多。 如果正确答案是满足

部分点

针对此问题设置了部分分数。

  • 1 ≦ N ≦ 50的数据集 给出 10 点。 如果正确答案是满足
  • 1 ≦ N ≦ 500的数据集,则进一步 给出 20 点。总共30点。
  • 1 ≦ N ≦ 5,000 的数据集,则进一步 给出 70 点。总共100点。

出力

输出中的行数为 3 等于该类型的查询数量。 i 在线 i 第 3 输出查询类型的答案。 范围内的最大值 M和号码 C 按此顺序输出 M, C ,用空格分隔。 在输出末尾插入换行符。


输入示例 1 的解释有错误,所以我将其替换为正确的 (21:51) 处理完第

入力例1

4 4
1 1 4 2
3 0 1 2 3
2 -2 1 3
3 0 3 1 3

出力例1

2 4
5 7

1 个查询后,方格纸将如下所示: 第

2 次查询的范围如下。

因此,最大值为 2,号码是 将会有 4 块。

3 个查询后,方格纸将如下所示: 第

4 次查询的范围如下。

因此,最大值为 5,号码是 将会有 7 块。


入力例2

50 20
2 5 40 6
1 69 94 5
3 8 39 31 32
2 -29 -21 -10
2 20 43 3
2 -37 36 -10
2 -18 45 5
2 30 39 -2
3 0 1 19 33
3 27 47 0 43
3 0 1 28 39
1 90 97 0
2 -46 31 7
1 81 81 4
1 11 54 3
3 10 29 26 30
1 39 45 3
1 70 97 -4
3 24 46 14 34
3 1 18 48 48

出力例2

11 5
-5 1
14 8
0 3
5 82
16 2
10 5