居然继续沦落到写CV的题解的地步了。
这又是一道坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑题。
思路很简单。就是记a的列前缀和和b的行前缀和，每次询问的时候O(n)的扫一遍乘积累和。
但是，极限数据本地要跑3.2s。虽然我笔记本是慢，但是也不能这样玩我啊。交了好久都在tle。
最后想到一个常数优化的办法。因为每次是把一行或者一列的数都访问一遍，所以用一个指针把数组的那一行记下来。这样寻址会快一些。事实证明快了不只一些。
坑，哈哈。
#include <cstdio>
#include <cctype>
#include <memory.h>
#include <algorithm>
using namespace std;
typedef long long qw;
#ifdef WIN32
#define lld "%I64d"
#else
#define lld "%lld"
#endif
#define _l (qw)
#define readInt(_s_) {\
int _d_;\
_s_ = 0;\
while (!isdigit(_d_ = getchar()));\
while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar()));\
}
const int maxn = 2001;
int a[maxn][maxn], b[maxn][maxn], n, m;
int main() {
readInt(n);
readInt(m);
for (int i = 1; i <= n; ++ i)
a[0][i] = 0, b[i][0] = 0;
for (int i = 1; i <= n; ++ i)
for (int j = 1; j <= n; ++ j) {
readInt(a[i][j]);
a[i][j] += a[i - 1][j];
}
for (int i = 1; i <= n; ++ i)
for (int j = 1; j <= n; ++ j)
readInt(b[j][i]);
for (int i = 1; i <= n; ++ i)
for (int j = 1; j <= n; ++ j)
b[i][j] += b[i - 1][j];
++ m;
while (-- m) {
int p, q, r, s;
readInt(p);
readInt(q);
readInt(r);
readInt(s);
if (p > r)
swap(p, r);
if (q > s)
swap(q, s);
-- p;
-- q;
qw ans = 0;
int *x0 = a[r], *x1 = a[p];
int *y0 = b[s], *y1 = b[q];
for (int i = 1; i <= n; ++ i)
ans += (_l x1[i] - x0[i]) * (y1[i] - y0[i]);
printf(lld "\n", ans);
}
}