【hdu 6336】 Matrix from Arrays

【链接】 我是链接,点我呀:)

【题意】

在这里输入题意

【题解】

找个规律会发现
M[i][j] = M[i-2*L][j] = M[i][j-2*L]
先预处理出来(1,1)-(2L,2L)这个矩阵以及他的二维前缀和

那么对于要求的(x0,y0)-(x1,y1)这个矩阵。

可以用若干个(1,1)-(x,y)这样的前缀矩阵通过加加减减算出来。

对于(1,1)-(x,y)这样的矩阵。

显然是由若干个(1,1)-(2L,2L)矩阵合并而成的(x/L)*(y/L)个。

多余的部分(下边,右下角以及右边)也能很快的求得。(利用(1,1)-(2L,2L)这个矩阵的前缀和

【代码】

#include <bits/stdc++.h>

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define all(x) x.begin(),x.end()

#define pb push_back

#define lson l,mid,rt<<1

#define rei(x) scanf("%d",&x)

#define rel(x) scanf("%lld",&x)

#define res(x) scanf("%s",x)

#define rson mid+1,r,rt<<1|1

using namespace std;

const double pi = acos(-1);

const int dx[4] = {0,0,1,-1};

const int dy[4] = {1,-1,0,0};

const int MAXL = 10;

int L,A[MAXL+10],M[MAXL*2+10][MAXL*2+10];

void creat_M(){

    int cursor = 0,cnt = 0;

    for (int i = 0;;++i){

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

            int x = j+1,y = i-j+1;

            if (x>=1 && x<= 2*L && y>=1 && y<=2*L) {

                M[x][y] = A[cursor];

                cnt++;

                if (cnt==4*L*L){

                    return;

                }

            }

            cursor = (cursor + 1)%L;

        }

    }

}

LL calc(int x,int y){

    LL temp1 = 1LL*M[L][L]*(x/L)*(y/L);

    LL temp2 = 1LL*M[x%L][L]*(y/L);

    LL temp3 = 1LL*M[L][y%L]*(x/L);

    LL temp4 = M[x%L][y%L];

    return temp1+temp2+temp3+temp4;

}

int main(){

	#ifdef LOCAL_DEFINE

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

	#endif

    ios::sync_with_stdio(0),cin.tie(0);

    int T;

    cin >> T;

    while (T--){

        cin >> L;

        rep1(i,0,L-1) cin >> A[i];

        memset(M,0,sizeof M);

        creat_M();

        rep1(i,1,2*L)

            rep1(j,1,2*L)

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

        L*=2;

        int Q;

        cin >> Q;

        while (Q--){

            int xx0,yy0,xx1,yy1;

            cin >> xx0 >> yy0 >> xx1 >> yy1;

            xx0++;yy0++;xx1++;yy1++;

            LL ans = calc(xx1,yy1)-calc(xx0-1,yy1)-calc(xx1,yy0-1)+calc(xx0-1,yy0-1);

            cout<<ans<<endl;

        }

    }

	return 0;

}