题解: 对于表达式用前缀和优化 n^2预处理 n*m查询
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define link(x) for(edge *j=h[x];j;j=j->next)
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
const int MAXN=2e3+10;
const double eps=1e-8;
#define ll long long
using namespace std;
struct edge{int t;edge*next;}e[MAXN<<1],*h[MAXN],*o=e;
void add(int x,int y){o->t=y;o->next=h[x];h[x]=o++;}
ll read(){
ll x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return x*f;
}
int sum1[MAXN][MAXN],sum2[MAXN][MAXN],a[MAXN][MAXN],b[MAXN][MAXN];
int n,m;
int main(){
n=read();m=read();
inc(i,1,n)inc(j,1,n)a[i][j]=read();
inc(i,1,n)inc(j,1,n)b[i][j]=read();
inc(i,1,n)inc(j,1,n)sum1[j][i]=sum1[j-1][i]+a[j][i];
inc(i,1,n)inc(j,1,n)sum2[i][j]=sum2[i][j-1]+b[i][j];
int x1,y1,x2,y2;
ll ans=0;
while(m--){
ans=0;
x1=read();y1=read();x2=read();y2=read();
if(x1>x2)swap(x1,x2);
if(y1>y2)swap(y1,y2);
inc(i,1,n)ans+=1LL*(sum1[x2][i]-sum1[x1-1][i])*(sum2[i][y2]-sum2[i][y1-1]);
printf("%lld
",ans);
}
return 0;
}
2901: 矩阵求和
Time Limit: 20 Sec Memory Limit: 256 MBSubmit: 610 Solved: 335
[Submit][Status][Discuss]
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。