Description：

矩形加 $+$ 矩形求和。

$1\le n,m \le 2018$

Solution：

二维树状数组，修改直接差分，设 $d$ 是差分数组，询问时，每个位置的值是 $\begin{align}\sum_{i=1}^x\sum_{j=1}^yd[i][j]\end{align}$ 前缀和实际上是 $\begin{align}\sum_{i=1}^x\sum_{j=1}^y\sum_{r=1}^i\sum_{c=1}^jd[r][c]\end{align}$ ，统计一下每个位置被计算了多少次，就会发现 $d[r][c]$ 被计算了 $(x-r+1)\times(y-c+1)$ 次，原式 $\begin{align}=\sum_{i=1}^x\sum_{j=1}^yd[i][j]\times(x-i+1)\times(y-j+1)\end{align}$ 。暴力展开的话就是 $\begin{align}\sum_{i=1}^x\sum_{j=1}^y(d[i][j]\times (xy+x+y+1)-d[i][j]\times i\times(y+1)-d[i][j]\times j\times (x+1)+d[i][j]\times ij)\end{align}$

于是维护 $d[i][j],d[i][j]\times i,d[i][j]\times j,d[i][j]\times ij$ 就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline char getc()

{

	register char c = getchar();

	while(c != 'X' && c != 'L' && c != 'k')c = getchar();

	return c;

}

inline int read()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

#define MAXN 2050

int n,m;

int d[MAXN][MAXN],di[MAXN][MAXN],dj[MAXN][MAXN],dij[MAXN][MAXN];

inline int lowbit(int x){return x & (-x);}

inline void add(int a,int b,int k)

{

	if(a == 0 || b == 0)return;

	for(register int i = a;i <= n;i += lowbit(i))

	{

		for(register int j = b;j <= m;j += lowbit(j))

		{

			d[i][j] += k;

			di[i][j] += k * a;

			dj[i][j] += k * b;

			dij[i][j] += k * a * b;

		}

	}

	return;

}

inline int query(int a,int b)

{

	if(a == 0 || b == 0)return 0;

	register int res = 0;

	for(register int i = a;i >= 1;i -= lowbit(i))

	{

		for(register int j = b;j >= 1;j -= lowbit(j))

		{

			res += d[i][j] * (a * b + a + b + 1) - di[i][j] * (b + 1) - dj[i][j] * (a + 1) + dij[i][j];

		}

	}

	return res;

}

int main()

{

	char ch[2];getc();

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

	register int a,b,c,d,k;

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

	{

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

		{

			a = read();b = read();c = read();d = read();k = read();

			if(a > c)swap(a,c);if(b > d)swap(b,d);

			add(a,b,k);add(c + 1,d + 1,k);add(a,d + 1,-k);add(c + 1,b,-k);

		}

		else

		{

			a = read();b = read();c = read();d = read();

			register int res = query(c,d) - query(c,b - 1) - query(a - 1,d) + query(a - 1,b - 1);

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

		}

	}

	return 0;

}