题意：
给定$n \times m$的矩阵，$k$个操作，每个操作给定矩阵左上角和右下角顶点，有两种操作，一是将该矩阵全部元素加上$x$，二是询问该矩阵全部元素的和。
数据范围：$0 \le n,m \le 2048, k \le 200000, 0 \le x \le 500$，保证计算过程中所有数不超过带符号整型。
分析:
区间求和问题我们可以转化为前缀和问题，即对于$[a,b]和[c,d]$之间的矩阵答案为$sum(c,d)-sum(c, b-1)-sum(a-1,d)+sum(a,b)$，这样就可以变为单点查询。
对于区间修改问题，我们利用差分的思想，将区间修改转化为单点修改。
令每个位置的元素为$newa_{i,j} = a_{i,j}-a_{i-1,j}-a_{i,j-1}+a_{i-1,j-1}$，那么$a_{x,y}=\sum_{i=1}^x \sum_{j=1}^y newa_{i,j}$
$sum(a,b)=\sum_{x=1}^a\sum_{y=1}^b a_{x,y}=\sum_{x=1}^a\sum_{y=1}^b \sum_{i=1}^x \sum_{j=1}^y newa_{i,j}$
考虑$[1,1]$内每个元素对于$sum(a,b)$的贡献，
$sum(a,b)=\sum_{i=1}^a\sum_{j=1}^b (a + 1 - i) \times (b + 1 - j) \times newa_{x,y} $
$= (a+1) \times (b+1)\sum_{i=1}^a\sum_{j=1}^b newa_{i,j}- (a+1) \sum_{i=1}^a\sum_{j=1}^b newa_{i,j}\times j-(b+1)\sum_{i=1}^a\sum_{j=1}^b newa_{i,j}\times i$
$+ \sum_{i=1}^a\sum_{j=1}^b i \times j \times newa_{i,j}$
这样对于每个点分别记录这四个值，单点更新单点查询套个二维树状数组即可。
代码：
|
|