题目大意

　　维护一个\(n\times m\)的矩阵，有两种操作：

　　　\(1~x_1~y_1~x_2~y_2~v\)：把\((a,b),(c,d)\)为顶点的矩形区域内的所有数字加上\(v\)。

　　　\(2~x_1~y_1~x_2~y_2\)：求\((a,b),(c,d)\)为顶点的矩形区域内所有数字的和。

　　\(n,m\leq 2048\)，操作数\(q\leq 200000\)，保证运算过程中及最终结果均不超过32位带符号整数类型的表示范围

题解

　　二维树状数组区间修改+区间求和模板题

　　区间修改+区间求和

　　时间复杂度：\(O(q\log n\log m)\)

代码

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<cstdlib>

#include<ctime>

#include<utility>

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

int c1[2100][2100];

int c2[2100][2100];

int c3[2100][2100];

int c4[2100][2100];

int n,m;

void add(int c[2100][2100],int x,int y,int v)

{

	int i,j;

	for(i=x;i<=n;i+=i&-i)

		for(j=y;j<=m;j+=j&-j)

			c[i][j]+=v;

}

int sum(int c[2100][2100],int x,int y)

{

	int i,j;

	int s=0;

	for(i=x;i;i-=i&-i)

		for(j=y;j;j-=j&-j)

			s+=c[i][j];

	return s;

}

void add(int x1,int y1,int x2,int y2,int v)

{

	add(c1,x1,y1,v); add(c1,x1,y2+1,-v); add(c1,x2+1,y1,-v); add(c1,x2+1,y2+1,v);

	add(c2,x1,y1,v*y1); add(c2,x1,y2+1,-v*(y2+1)); add(c2,x2+1,y1,-v*y1); add(c2,x2+1,y2+1,v*(y2+1));

	add(c3,x1,y1,v*x1); add(c3,x1,y2+1,-v*x1); add(c3,x2+1,y1,-v*(x2+1)); add(c3,x2+1,y2+1,v*(x2+1));

	add(c4,x1,y1,v*x1*y1); add(c4,x1,y2+1,-v*x1*(y2+1)); add(c4,x2+1,y1,-v*(x2+1)*y1); add(c4,x2+1,y2+1,v*(x2+1)*(y2+1));

}

int sum(int x,int y)

{

	return (x+1)*(y+1)*sum(c1,x,y)-(x+1)*sum(c2,x,y)-(y+1)*sum(c3,x,y)+sum(c4,x,y);

}

int sum(int x1,int y1,int x2,int y2)

{

	return sum(x2,y2)-sum(x2,y1-1)-sum(x1-1,y2)+sum(x1-1,y1-1);

}

int main()

{

	memset(c1,0,sizeof c1);

	memset(c2,0,sizeof c2);

	memset(c3,0,sizeof c3);

	memset(c4,0,sizeof c4);

	char s[5];

	scanf("%s%d%d",s,&n,&m);

	while(~scanf("%s",s))

	{

		if(s[0]=='L')

		{

			int x1,y1,x2,y2,v;

			scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&v);

			add(x1,y1,x2,y2,v);

		}

		else

		{

			int x1,y1,x2,y2;

			int ans;

			scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

			ans=sum(x1,y1,x2,y2);

			printf("%d\n",ans);

		}

	}

	return 0;

}