O(nm) 的暴力？
#include<cstdio> #include<cstdlib> #include<algorithm> using namespace std; typedef long long ll; inline char nc(){ static char buf[100000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; } inline void read(int &x){ char c=nc(),b=1; for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1; for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b; } const int N=2005; int n,m; int A[N][N],B[N][N]; int main(){ int a,b,c,d; ll Ans=0; freopen("t.in","r",stdin); freopen("t.out","w",stdout); read(n); read(m); for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) read(A[i][j]),A[i][j]+=A[i-1][j]; for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) read(B[i][j]),B[i][j]+=B[i][j-1]; while (m--){ read(a); read(c); read(b); read(d); if (a>b) swap(a,b); if (c>d) swap(c,d); Ans=0; for (int k=1;k<=n;k++) Ans+=(ll)(A[b][k]-A[a-1][k])*(B[k][d]-B[k][c-1]); printf("%lld\n",Ans); } return 0; }