题目描述
这是一道模板题。
给定一个大小为 N \times MN×M 的零矩阵，直到输入文件结束，你需要进行若干个操作，操作有两类：
-
1 a b c d x，表示将左上角为 (a,b)(a,b)，右下角为 (c,d)(c,d) 的子矩阵全部加上 xx； -
2 a b c d，表示询问左上角为 (a,b)(a,b)，右下角为 (c,d)(c,d) 为顶点的子矩阵的所有数字之和。
输入格式
第一行一个字符和两个正整数 ，其中 n,mn,m 分别表示矩阵的行数与列数。
接下来若干行直到文件结束，均代表你需要进行的操作。
输出格式
对于每个 2 操作，输出一行代表查询的结果。
样例
样例输入
4 41 1 1 3 3 21 2 2 4 4 12 2 2 3 3
样例输出
12
数据范围与提示
对于 10\%10% 的数据，1 \le n,m \le 161≤n,m≤16，操作不超过 200200 个；对于 60\%60% 的数据，1 \le n,m \le 5121≤n,m≤512；对于 100\%100% 的数据，1 \le n,m \le 2048,\lvert x \rvert \le 5001≤n,m≤2048,∣x∣≤500，操作不超过 2\times 10^52×105 个，保证运算过程中及最终结果均不超过 6464 位带符号整数类型的表示范围，并且修改与查询的子矩阵存在。
#includeusing namespace std;const int N=2100;long long s1[N][N],s2[N][N],s3[N][N],s4[N][N];int n,m;int lowbit(int x){ return x&(-x);}void updata(int x,int y,long long z){ for(int i=x;i<=n;i+=lowbit(i)){ for(int j=y;j<=n;j+=lowbit(j)){ s1[i][j]+=z; s2[i][j]+=x*z; s3[i][j]+=y*z; s4[i][j]+=x*y*z; } }}long long sum(int x,int y){ long long res=0; for(int i=x;i>0;i-=lowbit(i)){ for(int j=y;j>0;j-=lowbit(j)){ res+=(x+1)*(y+1)*s1[i][j]-(y+1)*s2[i][j]-(x+1)*s3[i][j]+s4[i][j]; } } return res;}int main(){ while(scanf("%d %d",&n,&m)==2){ memset(s1,0,sizeof(s1)); memset(s2,0,sizeof(s2)); memset(s3,0,sizeof(s3)); memset(s4,0,sizeof(s4)); int k; while(scanf("%d",&k)==1){ if(k==1){ int a,b,c,d; long long x; scanf("%d %d %d %d %lld",&a,&b,&c,&d,&x); updata(a,b,x); updata(c+1,b,-x); updata(a,d+1,-x); updata(c+1,d+1,x); } else{ int x1,y1,x2,y2; scanf("%d %d %d %d",&x1,&y1,&x2,&y2); printf("%lld\n",sum(x2,y2)-sum(x1-1,y2)-sum(x2,y1-1)+sum(x1-1,y1-1)); } } } return 0;}