Skip to content

1307: 数方块

题目

题目描述

预处理是一种常见的方法,在进入解决问题的主体前,我们先找出数据的一些特定结构或者赋予他们一些特殊的性质,这样能够帮助我们更好地解决问题。当然,你也可以把这一步视作解决问题的一部分。

拉菲奥最近想要解决这样一个问题:对于一个m * n 的整数方阵,任意给出这个方阵中的两个坐标(a,b),(c,d),其中,第一维对应行,第二维对应列。

他想要知道这两个坐标之间的的数的和是多少。

即求所有满足a<=x<=c,b<=y<=d(x,y)坐标的值的和。你能帮他快速的解决这个问题吗?

输入格式

第一行输入三个数m n k ,表示方阵为mn 列,并且有k 次询问。

接下来m 行为方阵的输入。

再接下来的k 行问询问坐标的输入,每一行格式如下a b c d 分别起始坐标与终止坐标,保证起始坐标每一维都小于等于终止坐标对应维。坐标为$1-base$。

输出格式

对于询问,输出和。

样例输入

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

```

样例输出

18 28 66

数据范围

对于$100\%$ 的数据,$n,m <= 2000;k<= 20000$ 。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!