BZOJ_2901_矩阵求和

BZOJ_2901_矩阵求和_前缀和

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

Sample Output

661
388

【数据规模和约定】
对30%的数据满足，n <= 100。
对100%的数据满足，n <= 2000，m <= 50000，输入数据中矩阵元素 < 100，a，b，c，d <= n。

$\sum\limits_{i=1}^{x}\sum\limits_{j=1}^{y}\sum\limits_{k=1}^{n}A_{ik}*B_{kj}$

$=\sum\limits_{k=1}^{n}\sum\limits_{i=1}^{n}A_{ik}\sum\limits_{j=1}^{y}B_{kj}$

处理出前缀和之后每次O(n)查一遍。

代码：

// bzoj-judger-enable-ogay

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

int sa[2050][2050],sb[2050][2050],n,m;

char buf[100000],*p1=buf,*p2=buf;

#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)

__attribute__((optimize("-O998244353")))int rd() {

	int x=0; char s=nc();

	while(s<'0'||s>'9') s=nc();

	while(s>='0'&&s<='9') x=(x<<3)+(x<<1)+s-'0',s=nc();

	return x;

}

char pbuf[100000],*pp=pbuf;

__attribute__((optimize("-O998244353")))void push(const char ch) {

	if(pp-pbuf==100000) fwrite(pbuf,1,100000,stdout),pp=pbuf;

	*pp++=ch;

}

__attribute__((optimize("-O998244353")))void write(ll x) {

	static int sta[70];

	int top=0;

	do{sta[++top]=x%10,x/=10;}while(x);

	while(top) push(sta[top--]+'0');

	push('\n');

}

__attribute__((optimize("-O998244353")))ll qu(int x,int y,int z,int w) {

	int i;

	ll re=0;

	for(i=1;i<=n;i++) re+=ll(sa[z][i]-sa[x-1][i])*(sb[i][w]-sb[i][y-1]);

	return re;

}

__attribute__((optimize("-O998244353")))int main() {

	n=rd(); m=rd();

	register int i,j,x;

	for(i=1;i<=n;i++) {

		for(j=1;j<=n;j++) {

			x=rd(); sa[i][j]=sa[i-1][j]+x;

		}

	}

	for(i=1;i<=n;i++) {

		for(j=1;j<=n;j++) {

			x=rd(); sb[i][j]=sb[i][j-1]+x;

		}

	}

	int y,z,w;

	while(m--) {

		x=rd(); y=rd(); z=rd(); w=rd();

		if(x>z) swap(x,z); if(y>w) swap(y,w);

		write(qu(x,y,z,w));

	}

	fwrite(pbuf,1,pp-pbuf,stdout);

}

巴特西