1003. 边界主义

题目描述

Rimi 正在制作 PopiV。为此，她开始研究一种叫作边界主义的电子抽象画派。在边界主义中，画家不会直接描绘具体物体，而是从画布的左右边缘拖出色块，让它们在画布上互相覆盖。Rimi 准备在一张大小为 n × n的电子画布上作画。画布由 n2 个像素组成，其中第 x 列、第 y 行的像素记为 (x, y)。每个像素都有一个整数亮度 V (x, y)。最开始，所有像素的亮度均为 0。Rimi 会进行恰好 n 次上色操作。每次上色操作会给出五个整数

x1, x2, y1, y2, v， 这表示她选中矩形区域 [x1, x2 ] × [y1, y2 ] 中的所有像素，并将它们的亮度提高到至少 v。

形式化地，对于所有满足 x1 ≤ x ≤ x2, y1 ≤ y ≤ y2 的像素 (x, y)，

执行 V (x, y) ← max(V (x, y), v)。由于边界主义的作画规则，每个色块必须从画布的左边界或右边界延伸出来。因此，对于每一次上色操作，都保证 x1 = 1 或者 x2 = n。

完成所有上色操作后，Rimi 想要检查画面中若干个矩形区域的整体亮度。她会提出 m 次询问。每次询问给出四个整数 x1, x2, y1, y2，你需要回

x

y

22答矩形区域中所有像素最终亮度之和，即 ∑x=x∑y=yV (x, y)。11

输入格式

第一行一个整数 T (1 ≤ T ≤ 50)，表示数据的组数。对于每组数据：第一行两个整数 n, m (1 ≤ n, m ≤ 2 × 105 )；

接下来 n 行每行五个整数 x1, x2, y1, y2, v，依次表示每次上色操作；

接下来 m 行每行四个整数 x1, x2, y1, y2，依次表示每次查询操作；

每个修改或查询操作均满足 1 ≤ x1 ≤ x2 ≤ n, 1 ≤ y1 ≤ y2 ≤ n。

每个修改操作均满足 1 ≤ v ≤ n，且保证 x1 = 1 或者 x2 = n。

对于所有数据，保证 n 的总和和 m 的总和均不超过 106。

输出格式

对于每组数据，输出 m 行，依次表示每次查询操作的答案。

样例输入

1
10 10
1 3 4 5 9
8 10 4 8 10
1 10 2 4 7
8 10 2 8 6
10 10 4 7 2
1 4 1 9 2
1 3 1 4 9
1 10 8 9 7
3 10 5 6 3
6 10 1 6 2
8 10 3 6
1 10 2 9
9 9 4 5
2 3 4 6
1 10 7 10
2 9 4 5
9 9 3 4
1 2 3 10
1 8 2 9
4 6 8 10

样例输出

111
542
20
41
187
116
17
90
400
42

提示

本题输入输出量较大，建议使用较快速的输入输出方式（如关闭流同步的 cin / cout）。

来源：官方题面 PDF（2026"钉耙编程"暑期联赛 第1场）