hdu6336 多校第四场E题 Matrix from Arrays

首先打表找出规律，它是以边长为2*n的正方形为一个周期向下和后扩散的，所以将周期的下标存到二维数组中，然后对于每个询问，求出完整周期有多少个，然后不完整的单独算即可。solve函数求的是(0,0)到(x,y)的和.

所以结果就是:

solve(x2,y2)-solve(x2,y1-1)-solve(x1-1,y2)+solve(x1-1,y1-1);

 

#pragma GCC optimize(2)
#include<stdio.h>
#include<string.h>
#include<string>
#include<math.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<stdlib.h>
#include<time.h>
#include <iomanip>
#define lowbit(x) (x&(-x))
#define inf  0x7fffffff
#define linf 0x7fffffffffffffff
#define mem(x,y) memset(x,y,sizeof(x))
#define fup(i,x,y) for(int i=(x);i<=(y);i++)
#define fdn(i,x,y) for(int i=(x);i>=(y);i--)
#define sp(x) setprecision(x)
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d%d",&n,&m)
#define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define sld(n) scanf("%lld",&n)
#define sldd(n,m) scanf("%lld%lld",&n,&m)
#define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k)
#define sf(n) scanf("%lf",&n)
#define sff(n,m) scanf("%lf%lf",&n,&m)
#define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k)
#define sc(n) scanf("%s",n)
#define pf(x) printf("%d\n",x)
#define pfl(x) printf("%lld\n",x)
#define pff(x) printf("%lf\n",x)
#define debug printf("!!\n");
#define N 100005
#define M 4000009
#define pi acos(-1)
#define eps 1e-2
//cout.setf(ios::fixed);
//freopen("out.txt","w",stdout);// freopen("in.txt","r",stdin);
using namespace std;
typedef long long  ll;
typedef long long  LL;
typedef double db;
int a[135][135],b[15],m,n;
int ini()
{
    int cursor = 0;
    for (int i = 0; i<=100; ++i)
    {
        for (int j = 0; j <= i; ++j)
        {
            a[j][i - j] = cursor+1;
            cursor = (cursor + 1) % n;
        }
    }
}
ll solve(ll x,ll y)
{
    if(x<0||y<0) return 0;
    ll ans=0;
    m=2*n;
    ll cnt=((x+1)/m)*((y+1)/m);

    if(cnt)
    {
       fup(i,0,2*n-1)
            fup(j,0,2*n-1)
                ans+=b[a[i][j]];
        ans*=cnt;
    }
    else
    {
        if((x+1)/m)
        {
            fup(i,0,2*n-1)
                fup(j,0,(y+1)%m-1)
                    ans+=b[a[i][j]];
            ans*=((x+1)/m);
            fup(i,0,(x+1)%m-1)
                fup(j,0,(y+1)%m-1)
                    ans+=b[a[i][j]];
        }
        else if((y+1)/m)
        {
            fup(i,0,(x+1)%m-1)
                fup(j,0,2*n-1)
                    ans+=b[a[i][j]];
            ans*=((y+1)/m);
            fup(i,0,(x+1)%m-1)
                fup(j,0,(y+1)%m-1)
                    ans+=b[a[i][j]];
        }
        else
        {
            fup(i,0,x)
                fup(j,0,y)
                    ans+=b[a[i][j]];
        }
        return ans;
    }
    ll sum1=0;
    fup(i,0,(x+1)%m-1)
        fup(j,0,2*n-1)
            sum1+=b[a[i][j]];
    ans+=(sum1*((y+1)/m));

    sum1=0;

    fup(i,0,2*n-1)
        fup(j,0,(y+1)%m-1)
            sum1+=b[a[i][j]];
    ans+=(sum1*((x+1)/m));

    fup(i,0,(x+1)%m-1)
        fup(j,0,(y+1)%m-1)
            ans+=b[a[i][j]];

    return ans;

}
int main()
{
    int t;
    sd(t);
    while(t--)
    {
        sd(n);
        fup(i,1,n)
            sd(b[i]);
        int q;
        ini();
        sd(q);
        while(q--)
        {
            int x1,x2,y1,y2;
            sdd(x1,y1);
            sdd(x2,y2);
            ll ans=solve(x2,y2)-solve(x2,y1-1)-solve(x1-1,y2)+solve(x1-1,y1-1);
            pfl(ans);
        }
    }
}