1.3 KiB
1.3 KiB
矩形加矩形求和（离线）
题目描述
一个 h\times w 网格，首先有 q1 次矩形加操作：
(r1,r2,c1,c2,x)代表给左上角 $(r1,c1)$、右下角(r2,c2)的矩形区域加x
接下来有 q2 次矩形求和查询：
(r1,r2,c1,c2)代表询问左上角 $(r1,c1)$、右下角(r2,c2)的矩形区域的和，对 2021 取模
输入格式
第一行4个整数 h,w,q1,q2
接下来 q1 行，每行5个整数 (r1,r2,c1,c2,x) 代表一次矩形加
接下来 q2 行，每行4个整数 (r1,r2,c1,c2) 代表一次矩形求和
输出格式
输出 q2 行，对于每次查询输出一行一个整数代表答案
样例 #1
样例输入 #1
5 4 3 5
1 3 1 3 3
3 4 1 4 4
1 5 1 2 0
2 4 1 2
4 5 1 1
3 4 2 4
1 4 1 1
1 2 1 1
样例输出 #1
28
4
30
17
6
样例 #2
样例输入 #2
见下发样例
样例输出 #2
样例 #3
样例输入 #3
见下发样例
样例输出 #3
提示
对于 100% 的数据，1\le h,w\le 10^9,1\le q1,q2\le 10^5， 1\le r1\le r2\le h, 1\le c1\le c2\le w, 0\le x<2021
subtask1(25pts): h = 1, 1\le w \le 10^9
subtask2(25pts): 1\le h,w\le 500
subtask3(25pts): h\le 500,1\le w \le 10^9, q1\le 10000
subtask5(25pts):无特殊限制