HDU - 6336 Problem E. Matrix from Arrays （规律+二维前缀和）

题意：

for (int i = 0; ; ++i) {
    for (int j = 0; j <= i; ++j) { 
        M[j][i - j] = A[cursor];
        cursor = (cursor + 1) % L;
    }
}

给定序列A[1..L]，二维数组M的规律由以上代码给出。Q个查询，每次给x0,y0,x1,y1 (0≤x0≤x1≤1e8,0≤y0≤y1≤1e8)四个数，求以（x0,y0）和（x1,y1）两个点为端点的矩形中数的和。

分析：根据推导可得，M[i][j] = M[i+2L][j] + M[i][j+2L]。当L为奇数时，每个L*L的块都是一个循环节；L为偶数时，每个2*L*2*L是一个循环节，可以打表验证。

预处理出M[i][j]一个循环节的的二维前缀和，复杂度O(L^2)。每次计算答案可以由前缀和相加减所得：S(x1,y1)  - S(x1,y0-1) - S(x0-1, y1) + S(x0-1,y0-1)。

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int maxn = 2e2+;

LL M[maxn][maxn];

int A[maxn];

int L;

LL area(int x,int y){

    LL block = M[L-][L-];         //一个块的和

    LL res=block *(x/L)*(y/L);

    res+=M[x%L][y%L];

    res+=(x/L)*M[L-][y%L];

    res+=(y/L)*M[x%L][L-];

    return res;

}

int main()

{

    #ifndef ONLINE_JUDGE

         freopen("in.txt","r",stdin);

         freopen("out.txt","w",stdout);

    #endif

    int T,N,Q,u,v,tmp,K;

    scanf("%d",&T);

    while(T--){

        scanf("%d",&N);

        for(int i=;i<N;++i)

            scanf("%d",&A[i]);

        if(N&) L =N*;

        else L = (N<<);

        int cur = ;

        for(int i=;i<L;++i){

            for(int j=;j<=i;++j){

                M[j][i-j] = A[cur];

                cur  = (cur+) %N;

            }

        }

        L/=;

        for(int i=;i<L;++i){

            for(int j=;j<L;++j){

                M[i][j] +=M[i][j-];

                M[i][j] +=M[i-][j];

                M[i][j] -=M[i-][j-];

            }

        }

        scanf("%d",&Q);

        while(Q--){

            int a,b,c,d;

            scanf("%d%d%d%d",&a,&b,&c,&d);

            LL res = area(c,d)+area(a-,b-)-area(c,b-)-area(a-,d);

            printf("%lld\n",res);

        }

    }

    return ;

}

HDU - 6336 Problem E. Matrix from Arrays （规律+二维前缀和）的相关教程结束。