给出两个n*n的矩阵，m次询问它们的积中给定子矩阵的数值和。 对100%的数据满足，n <= 2000，m <= 50000，输入数据中矩阵元素 < 100，a，b，c，d <= n。
所求结果为\[ans=\sum_{i=a}^{c}\sum_{j=b}^{d}z_{ij}\] 观察式子\[z_{ij}=\sum_{k=1}^{n}x_{ik}y_{kj}\] 那么结果就是\[ans=\sum_{i=a}^{c}\sum_{j=b}^{d}\sum_{k=1}^{n}x_{ik}y_{kj}\] 简单交换律之后就是\[ans=\sum_{k=1}^{n}(\sum_{i=a}^{c}x_{ik}\sum_{j=b}^{d}y_{kj})\] \(\sum_{i=a}^{c}x_{ik}\sum_{j=b}^{d}y_{kj}\)这里显然可以使用前缀和进行处理 于是每个答案就是\(O(n)\)求出
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| #include<bits/stdc++.h>
using namespace std;
inline int ReadInt()
{
int x=0,f=1; char ch=getchar();
while (ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
while (ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
int n,m;
int x[2010][2010]={};
int y[2010][2010]={};
int o;
long long ans=0;
int main()
{
n=ReadInt();
m=ReadInt();
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
o=ReadInt();
x[i][j]=x[i-1][j]+o;
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
o=ReadInt();
y[i][j]=y[i][j-1]+o;
}
}
int a,b,c,d;
for(int i=1;i<=m;i++)
{
a=ReadInt();
b=ReadInt();
c=ReadInt();
d=ReadInt();
if(c<a) swap(a,c);
if(d<b) swap(b,d);
ans=0ll;
for(int j=1;j<=n;j++)
{
long long g,h;
h=x[c][j]-x[a-1][j];
g=y[j][d]-y[j][b-1];
ans+=h*g;
}
printf("%lld\n",ans);
}
return 0;
}
|