欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【hdu 6336】 Matrix from Arrays

程序员文章站 2022-07-12 09:31:36
...

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


在这里输入题意

【题解】


找个规律会发现
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;
}