BZOJ_2901_矩阵求和_前缀和

// 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);
}