差分 - 谁多谁闪亮

题目背景

外星人来地球游玩，他们到达某个贫困的小县城，这里有n * m个小村庄整齐排列着，外星人一看是个矩形排列，一下子来了兴趣，想在这里游玩，但无奈，已经天黑，没有一点灯光，他们只能使用法术，将某些村庄照亮。说来外星人也是很有礼貌的，他们也模仿着村庄的样子，每次给某些a * b矩形的小村庄加亮x点灯光，那么现在问题来了，当一系列魔法完成之后，那么问题来了，你知道最后哪个具体的村庄灯光有多少点吗？假设某个村庄获得x点灯光后就不会消失，且多次获得灯光的点数是累加的,刚开始每个村庄的灯光为0点。

题目描述

同上

输入格式

每一行2个整数n和m,用空格隔开，表示村庄的行列数每二行一个整数t,表示有t组操作，对某些矩形实施点亮法术。(1<=t<=100000)

接下来t行，每行有5个整数，分别为x , lenx , y , leny , k 分别表示将矩形村庄的第x行到第x+lenx-1行，第y列到第y+leny-1列的所有村庄加亮k点永不消失的灯光。

接下来一个整数h，表示想问h次关于某个村庄灯光的点数(1<=h<=100000)

接下来h行，每行两个用空格隔开的整数x,y, 表示询问第x行，y列村庄点数情况（1<=n,m<=2000）

输出格式

对于输入的后h行询问，输出对应的h行，每行一个整数，表示该村庄的灯光点数。

样例

输入样例：

10 10

2

1 6 1 6 3

1 7 1 7 5

2

5 5

7 7

输出样例：

8
5

#include<bits/stdc++.h>
using namespace std;
int f[2005][2005];
int n,m,t;
int main()
{
	cin>>n>>m>>t;
	for(int i=1;i<=t;i++)
	{
		int x,y,lenx,leny,k;
		scanf("%d%d%d%d%d",&x,&lenx,&y,&leny,&k);
		f[x][y]+=k;
		f[x][y+leny]-=k;
		f[x+lenx][y]-=k;
		f[x+lenx][y+leny]+=k;
	}
	for(int i=1;i<=n;i++)
	 for(int j=1;j<=m;j++)
	  f[i][j]+=f[i-1][j]+f[i][j-1]-f[i-1][j-1];
	  cin>>t;
	for(int i=1;i<=t;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		printf("%d\n",f[x][y]);
	}
	return 0;   
}