Problem E. Matrix from Arrays

打表发现是2L*2L 的矩阵重复出现，然后预处理2L*2L的矩阵的前缀和就行了，之后求一下有多少完整的矩形，有多少一部分矩形的


#include <bits/stdc++.h>
#define mem(ar,num) memset(ar,num,sizeof(ar))
#define me(ar) memset(ar,0,sizeof(ar))
#define lowbit(x) (x&(-x))
#define Pb push_back
#define FI first
#define SE second
#define For(i,a,b) for(int i = a; i < b; ++i)
#define IOS ios::sync_with_stdio(false)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int    prime = 999983;
const int    INF = 0x7FFFFFFF;
const LL     INFF =0x7FFFFFFFFFFFFFFF;
const double pi = acos(-1.0);
const double inf = 1e18;
const double eps = 1e-6;
const LL     mod = 1e9 + 7;
LL qpow(LL a,LL b){LL s=1;while(b>0){if(b&1)s=s*a%mod;a=a*a%mod;b>>=1;}return s;}
LL gcd(LL a,LL b) {return b?gcd(b,a%b):a;}
int dr[2][4] = {1,-1,0,0,0,0,-1,1};
typedef pair<int,int> P;
const int maxn = 100;
int A[maxn];

LL M[maxn][maxn]; 
LL S[maxn][maxn];
int n ,L ;
LL L2;
void Print(LL M[][maxn]){
    for(int i = 0;i < 2*L; ++i,cout<<endl)
      for(int j = 0;j < 2*L; ++j)
         printf("%5lld ",M[i][j]) ;
}
void init(void){

        n = 4*L;
        L2 = 2*L;
        int cursor = 0;
        for(int i = 0;i < n; ++i ){
            for(int j = 0;j <= i; ++j){
                M[j][i-j] = A[cursor];
                cursor = (cursor+1)% L;
            }
        }
// S[0][0] = M[0][0]; 
// for(int i = 1;i < L2; ++i)
// S[i][0] = S[i-1][0]+M[i][0];
// for(int i = 1;i < L2; ++i)
// S[0][i] = S[0][i-1]+M[0][i];
    //me(S);
        for(int i = 1;i <= L2; ++i){
             for(int j = 1;j <= L2; ++j){
                     S[i][j] = 0;
                      S[i][j] = S[i-1][j]+S[i][j-1]-S[i-1][j-1]+M[i-1][j-1];
             }
        }
// 
// Print(M);
// Print(S); 
}

LL solve(LL x,LL y){
    x++,y++;
// cout<<x<<y<<endl;
    LL ans = 0;
    LL xx = x/L2, yy = y/L2;
// cout<<xx<<yy<<endl;
    LL xxx = x%L2,yyy = y % L2;
    // 整的 
    ans += xx*yy*S[L2][L2];
    // 右边
    ans += xx*S[L2][yyy];
    // 下边
    ans += yy*S[xxx][L2];
    // 角落
    ans += S[xxx][yyy]; 
// cout<<ans<<endl;
    return ans;
}

int main(void)
{
    int T;
    scanf("%d",&T);
    int cursor = 0;
    while(T--) {
        scanf("%d",&L);
        for(int i = 0;i < L; ++i)
          scanf("%d",&A[i]);
      init(); 
      int Q;
      scanf("%d",&Q);
      while(Q--){
        LL  x1,y1,x2,y2;
        scanf("%lld %lld %lld %lld",&x1,&y1,&x2,&y2);
        //cout<<x1<<y1<<x2<<y2<<endl;
// cout<<solve(x2,y2)<<endl;
// cout<<solve(x1-1,y2)<<endl;
// cout<<solve(x2,y1-1)<<endl;
// cout<<solve(x1,y1)<<endl;
        printf("%lld\n",solve(x2,y2)-solve(x1-1,y2)-solve(x2,y1-1)+solve(x1-1,y1-1));
      }
    }

   return 0;
}