Description

Input

Output

Sample Input

Sample Output

HINT

Source

2D树状数组支持单点修改+求和(1,1)-(x,y)矩形

因此按照zkw的思路用逆求和数组做(就是把区间修改结构-用2个单点修改的逆求和数组d',{i*d'}代替,神思路)

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
#define MAXN (2050)
int lowbit(int x){return x&(-x);}
int n,m,x1,x2,y1,y2,delta;
struct arr_tree
{
	int b[MAXN][MAXN];
	arr_tree(){memset(b,0,sizeof(b));	}
	void add(int x,int y,int c,bool b1,bool b2)
	{
		if (!x||!y||x>n||y>m) return;
		if (b1) c*=(x-1);if (b2) c*=(y-1);if (!c) return;
		for (int i=x;i<=n;i+=lowbit(i))
			for (int j=y;j<=m;j+=lowbit(j)) b[i][j]+=c;
	}
	int qur(int x,int y)
	{
		if (!x||!y) return 0;
		int ans=0;
		for (int i=x;i;i-=lowbit(i))
			for (int j=y;j;j-=lowbit(j)) ans+=b[i][j];
		return ans;
	}
	void add(int x1,int y1,int x2,int y2,int c,bool b1,bool b2)
	{
		add(x2+1,y2+1,delta,b1,b2),add(x1,y1,delta,b1,b2);
		add(x1,y2+1,-delta,b1,b2),add(x2+1,y1,-delta,b1,b2);
	}
}d,di,dj,dij;
int Dsum(int x,int y)
{
	return d.qur(x,y)*x*y+dij.qur(x,y)-di.qur(x,y)*y-dj.qur(x,y)*x;
}
int main()
{
	scanf("X %d %d",&n,&m);
	char c;
	while (scanf("%c",&c)==1)
	{
		while (c^'L'&&c^'k') if (scanf("%c",&c)!=1) return 0;
		switch(c)
		{
			case 'L':
				scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&delta);
				if (x1>x2) swap(x1,x2),swap(y1,y2);
				d.add(x1,y1,x2,y2,delta,0,0),di.add(x1,y1,x2,y2,-delta,1,0);
				dj.add(x1,y1,x2,y2,-delta,0,1),dij.add(x1,y1,x2,y2,delta,1,1);
				break;
			default:
				scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
				if (x1>x2) swap(x1,x2),swap(y1,y2);
				printf("%dn",Dsum(x2,y2)+Dsum(x1-1,y1-1)-Dsum(x1-1,y2)-Dsum(x2,y1-1));
		}
	}
}