题目详情题解（0）讨论（0）提交记录（0）

AT_arc047_d.[ARC047D] ナナメクエリ

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有一个 N×NN \times N 的方格纸。

我们将方格纸的最左上角定义为格子 (0,0)(0, 0)，最右下角为格子 (N−1,N−1)(N-1, N-1)。对任意格子 (X,Y)(X, Y)，其表示从最左上角格子向下移动 XX 格，向右移动 YY 格所到达的位置。

初始时，所有格子的值均为 00。

现在，需要对这张方格纸进行 QQ 次操作。操作类型共有三种，描述如下：

  1. 1 A B C：对所有满足 A≤X+Y≤BA \leq X+Y \leq B 的格子 (X,Y)(X, Y)，将其值增加 CC。保证 0≤A≤B≤2N−20 \leq A \leq B \leq 2N-2 且 −105≤C≤105-10^5 \leq C \leq 10^5。
  2. 2 A B C：对所有满足 A≤X−Y≤BA \leq X-Y \leq B 的格子 (X,Y)(X, Y)，将其值增加 CC。保证 1−N≤A≤B≤N−11-N \leq A \leq B \leq N-1 且 −105≤C≤105-10^5 \leq C \leq 10^5。
  3. 3 A B C D：在所有满足 A≤X≤BA \leq X \leq B 且 C≤Y≤DC \leq Y \leq D 的格子中，找出最大值 MM，并计算这些格子中写有 MM 的个数。保证 0≤A≤B≤N−10 \leq A \leq B \leq N-1 且 0≤C≤D≤N−10 \leq C \leq D \leq N-1。

你的任务是编写程序，依次处理这些查询操作。

输入格式

输入包含以下内容：

  • 第一行是两个整数 NN 和 QQ，分别表示方格纸的大小和查询的数量。保证 1≤N≤50001 \leq N \leq 5000 且 1≤Q≤50001 \leq Q \leq 5000。
  • 接下来的 QQ 行，每行对应一个查询操作。格式如同题目描述。
  • 至少有一个查询是类型为 3 的。

输出格式

输出的行数应与类型为 3 的查询数量相等。对于第 ii 个类型为 3 的查询，请输出其结果。结果需包括该范围内的最大值 MM 和该值的出现次数，格式为 "M CM\ C"（中间用空格分隔）。注意，每行末尾需要有一个换行符。

输入输出样例

  • 输入#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

  • 输入#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

说明/提示

部分得分

本题有设置部分得分：

  • 如果正确解答 1≤N≤501 \leq N \leq 50 的数据集，可以获得 1010 分。
  • 如果正确解答 1≤N≤5001 \leq N \leq 500 的数据集，可以额外获得 2020 分，总分达到 3030 分。
  • 如果正确解答 1≤N≤50001 \leq N \leq 5000 的数据集，可以再获得 7070 分，总分 100100 分。

本翻译由 AI 自动生成

输入解题思路，AI测评打分。不知道怎么写?

首页