Description
给出两个n*n的矩阵，m次询问它们的积中给定子矩阵的数值和。
Input
第一行两个正整数n，m。
接下来n行，每行n个非负整数，表示第一个矩阵。
接下来n行，每行n个非负整数，表示第二个矩阵。
接下来m行，每行四个正整数a，b，c，d，表示询问第一个矩阵与第二个矩阵的积中，以第a行第b列与第c行第d列为顶点的子矩阵中的元素和。
Output
对每次询问，输出一行一个整数，表示该次询问的答案。
Sample Input
3 2
1 9 8
3 2 0
1 8 3
9 8 4
0 5 15
1 9 6
1 1 3 3
2 3 1 2
1 9 8
3 2 0
1 8 3
9 8 4
0 5 15
1 9 6
1 1 3 3
2 3 1 2
Sample Output
661
388
【数据规模和约定】
对30%的数据满足，n <= 100。
对100%的数据满足，n <= 2000，m <= 50000，输入数据中矩阵元素 < 100，a，b，c，d <= n。
388
【数据规模和约定】
对30%的数据满足，n <= 100。
对100%的数据满足，n <= 2000，m <= 50000，输入数据中矩阵元素 < 100，a，b，c，d <= n。
时间限制20s
题解：一看这道题，自然想到能不能用前缀和直接搞，但是这样做可以吗？答案是可以的
时间复杂度O(nm)，还有此题必须加读入优化
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int maxn=2010;
int n,m;
long long ans;
int sx[maxn][maxn],sy[maxn][maxn];
int rd()
{
int ret=0; char gc=getchar();
while(gc<'0'||gc>'9') gc=getchar();
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret;
}
int main()
{
n=rd(),m=rd();
int i,j,a,b,c,d;
for(i=1;i<=n;i++) for(j=1;j<=n;j++) sx[i][j]=sx[i-1][j]+rd();
for(i=1;i<=n;i++) for(j=1;j<=n;j++) sy[i][j]=sy[i][j-1]+rd();
for(i=1;i<=m;i++)
{
a=rd(),b=rd(),c=rd(),d=rd(),ans=0;
if(a>c) swap(a,c);
if(b>d) swap(b,d);
for(j=1;j<=n;j++) ans+=(long long)(sx[c][j]-sx[a-1][j])*(sy[j][d]-sy[j][b-1]);
printf("%lld
",ans);
}
return 0;
}