#P15812. [2025年山东集训第三轮]我推的孩子

    ID: 15023 传统题 12000ms 512MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>数据结构分块并查集扫描线CF3200

[2025年山东集训第三轮]我推的孩子

题目描述

需要维护二维平面上的整点,每个整点 (x,y)(x,y) 有权值 V(x,y)V(x,y) ,初始为 00。

给定 nn 次修改操作,每次修改给出 x1,x2,y1,y2,vx_1,x_2,y_1,y_2,v ,对每个满足 x1≤x≤x2,  y1≤y≤y2x_1\le x\le x_2,\;y_1\le y\le y_2 的 (x,y)(x,y) ,将 V(x,y)V(x,y) 修改为 max⁡(V(x,y),v)\max(V(x,y),v) ;

在所有修改操作之后,有 mm 次查询操作,每次操作给出 x1,x2,y1,y2x_1,x_2,y_1,y_2 ,查询 $\sum\limits_{x=x_1}^{x_2}\sum\limits_{y=y_1}^{y_2}V(x,y)$ 。

输入格式

第一行两个整数 n,mn,m;

接下来 nn 行每行 55 个整数 x1,x2,y1,y2,vx_1,x_2,y_1,y_2,v ,依次表示每次修改操作;

接下来 mm 行每行 44 个整数 x1,x2,y1,y2x_1,x_2,y_1,y_2 ,依次表示每次查询操作。

输出格式

共 mm 行,依次表示每次查询操作的答案。

输入输出样例 #1

输入 #1

4 3
2 2 1 4 1
1 2 1 3 1
2 4 3 4 3
2 4 3 4 3
1 1 3 3
2 4 3 3
2 4 3 4

输出 #1

1
9
18

说明/提示

对于 20%20\% 的数据,满足 n,m≤100n,m\le 100。

对于另外 20%20\% 的数据,满足 m≤10m\le 10。

对于另外 20%20\% 的数据,满足 n,m≤5×104n,m\le 5\times 10^4。

对于 100%100\% 的数据,满足 1≤n,m≤2×1051\le n,m\le 2\times 10^5。

对每个修改或查询操作,满足 1≤x1≤x2≤n1\le x_1\le x_2\le n , 1≤y1≤y2≤n1\le y_1\le y_2\le n 。

对每个修改操作,满足 1≤v≤n1\le v\le n。

所有数值为整数。