一开始以为是一个高明的数据结构，后来发现直接拆式子就行了
举个$2*2$矩阵的例子
第一个矩阵
$$
\begin{bmatrix}
a_1 & a_2 \\
a_3 & a_4 \\
\end{bmatrix}
$$
第二个矩阵
$$
\begin{bmatrix}
b_1 & b_2 \\
b_3 & b_4 \\
\end{bmatrix}
$$
那么我们来乘一下，结果是
$$
\begin{bmatrix}
a_1*b_1+a_2*b_3 & a_2*b_4+a_1*b_2 \\
a_3*b_1+a_4*b_3 & a_4*b_4+a_3*b_2 \\
\end{bmatrix}
$$
加一下得到$a_1*(b_1+b_2)+a_2*(b_3+b_4)+a_3*(b_1+b_2)+a_4*(b_3+b_4)$
组合一下得到$(a_1+a_3)*(b_1+b_2)+(a_2+a_4)*(b_3*b_4)$
也就是第一个矩阵记录向上的前缀和，第二个矩阵记录向左的前缀和
然后乘一下就好了
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const register int N=2005;
static int n,m,a[N][N],b[N][N];
inline void Read(register int &x){
register char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
}
int main(){
freopen("2901.in","r",stdin);
freopen("2901.out","w",stdout);
Read(n);Read(m);
for(register int i=1;i<=n;i++)for(register int j=1;j<=n;j++)Read(a[i][j]),a[i][j]+=a[i-1][j];
for(register int i=1;i<=n;i++)for(register int j=1;j<=n;j++)Read(b[i][j]),b[i][j]+=b[i][j-1];
while(m--){
register int A,B,C,D;
Read(A);Read(B);Read(C);Read(D);
if(A>C)A^=C^=A^=C;
if(B>D)B^=D^=B^=D;
register long long ans=0;
for(register int i=1;i<=n;i++)ans+=(1ll*a[C][i]-a[A-1][i])*(1ll*b[i][D]-b[i][B-1]);
printf("%lld\n",ans);
}
return 0;
}
评论 (0)
