#1283. 二维前缀和模板

二维前缀和模板

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一个nm\red {n*m}的矩阵,矩阵中的元素都是整数。 给定k\red k个询问:a[i][j]\red {a[i][j]} 为左上角顶点,a[p][q]\red{a[p][q]}为右下角顶点所组成的小矩阵中,所有元素的和为多少。

输入格式

第一行为三个整数n\red n,m\red m,k\red k

接下来为一个n\red n * m\red m的矩阵。

接下来的k行,每行有四个整数i\red i,j\red j,p\red p,q\red q

输出格式

输出询问的矩形区域中,所有元素之和。

样例

输入样例

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

输出样例

8
27
5

数据范围与提示

对于所有的数据:1n,mk1000\red {1≤n,m,k≤1000}

对所有的数据:i<=p,j<=q\red {i<=p,j<=q}

对矩阵中的任意一个元素、任意一个区域的元素和,均不会超过long long 的表示范围。

添胜中级班(前缀和+差分+线筛)

未参加
状态
已结束
规则
IOI
题目
5
开始于
2023-8-6 9:00
结束于
2023-8-7 9:00
持续时间
24 小时
主持人
参赛人数
25