BZOJ-2901: 矩阵求和

Description

给出两个n*n的矩阵，m次询问它们的积中给定子矩阵的数值和。n <= 2000，m <= 50000

容斥之后，化简式子：

求两个矩阵的前缀和，每次询问容斥，每次O(n)求一下就行了。

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 2100 
#define R register 
typedef long long ll;
inline char nc()
{
    static char buf[100000],*p1,*p2;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
    int x=0; char ch=nc();
    while(!isdigit(ch)) ch=nc();
    while(isdigit(ch)) x=x*10+(ch^'0'),ch=nc();
    return x;
}
int n,m;
int m1[N][N],m2[N][N];
ll ans(int x,int y)
{
    ll re=0;
    for(R int i=1;i<=n;++i)
        re+=(ll)m1[x][i]*m2[i][y];
    return re;
}
int main()
{
    n=read(); m=read();
    R int i,j;
    for(i=1;i<=n;++i)
        for(j=1;j<=n;++j)
            m1[i][j]=read();
    for(i=1;i<=n;++i)
        for(j=1;j<=n;++j)
            m1[j][i]+=m1[j-1][i];
    for(i=1;i<=n;++i)
        for(j=1;j<=n;++j)
            m2[i][j]=read();
    for(i=1;i<=n;++i)
        for(j=1;j<=n;++j)
            m2[i][j]+=m2[i][j-1];
    int l1,l2,r1,r2;
    while(m--)
    {
        l1=read(); l2=read(); r1=read(); r2=read();
        if(l1>r1) swap(l1,r1);
        if(l2>r2) swap(l2,r2);
        printf("%lld\n",ans(r1,r2)-ans(r1,l2-1)-ans(l1-1,r2)+ans(l1-1,l2-1));
    }
    return 0;
}