Calzonification

Undead2008 · 2024-09-12 22:17:21 · 题解

这个生成方式不好刻画，考虑打表观察答案网格的性质。

打表可以发现对于大部分的 (i,j)，(i,j) 和 (i-1,j-1) 的颜色相同。事实上对于所有 i,j\ge 4，该性质成立。

证明一下。考虑对一个 4\times 4 的网格标号，如上图。我们想要证明 \tt 1 格子和 \tt 2 格子的颜色总是相等，不妨先考虑不等的情况：

所以 \tt 1 格子和 \tt 2 格子颜色总是相等，证明了上述结论。

所以我们暴力做前三行和前三列，之后的格子颜色都可以推出，查询时是一个等差序列求和，分讨一下即可。

#include"bits/stdc++.h"
using namespace std;
#define L long long
const int maxN = 200010;
const int B = 3;
int n,q,a[B+2][maxN],b[maxN][B+2];
int Mex[2][2];
inline int Geta(int Xl,int Yl,int Xr,int Yr){
    return a[Xr][Yr]-a[Xl-1][Yr]-a[Xr][Yl-1]+a[Xl-1][Yl-1];
}
inline int Getb(int Xl,int Yl,int Xr,int Yr){
    return b[Xr][Yr]-b[Xl-1][Yr]-b[Xr][Yl-1]+b[Xl-1][Yl-1];
}
int Id[maxN<<1],Idx;
L Su[maxN<<1],Sl[maxN<<1],Sr[maxN<<1];
inline L Cl(int l,int r){
    return (Sl[r]-Sl[l-1])-(Su[r]-Su[l-1])*(l-1);
}
inline L Cr(int l,int r){
    return (Sr[r]-Sr[l-1])-(Su[r]-Su[l-1])*(Idx-r);
}
inline int Origin(int X,int Y){
    int Dl=min(X-B,Y-B);
    X-=Dl,Y-=Dl;
    if(Y==B)return n-X+1;
    return n-B+1+Y-B;
}
inline L Solve(int Xl,int Yl,int Xr,int Yr){
    int Lb=Origin(Xr,Yl),Rb=Origin(Xl,Yr),Ln=min(Xr-Xl+1,Yr-Yl+1);
    return Cl(Lb,Lb+Ln-1)+(Su[Rb-Ln+1]-Su[Lb+Ln-1])*Ln+Cr(Rb-Ln+2,Rb);
}
vector<L> mosaic(vector<int> Xo,vector<int> Yo,vector<int> To,vector<int> Bo,vector<int> Lo,vector<int> Ro){
    n=Xo.size(),q=To.size();
    Mex[0][0]=1;
    vector<L>Ans;
    for(int i=1;i<=n;i++)a[1][i]=Xo[i-1];
    for(int j=1;j<=min(B,n);j++)a[j][1]=Yo[j-1];
    for(int j=B+1;j<=n;j++)b[j][1]=Yo[j-1];
    for(int i=2;i<=B;i++)
        for(int j=2;j<=n;j++)
            a[i][j]=Mex[a[i][j-1]][a[i-1][j]];
    for(int i=B+1;i<=n;i++)
        for(int j=2;j<=B;j++)
            b[i][j]=Mex[b[i][j-1]][(i==B+1?a[i-1][j]:b[i-1][j])];
    for(int j=n;j>B;j--)Su[++Idx]=b[j][B];
    for(int j=B;j<=n;j++)Su[++Idx]=a[B][j];
    for(int i=1;i<=Idx;i++)Sl[i]=Sl[i-1]+i*Su[i];
    for(int i=1;i<=Idx;i++)Sr[i]=Sr[i-1]+(Idx-i+1)*Su[i];
    for(int i=1;i<=Idx;i++)Su[i]=Su[i-1]+Su[i];
    for(int i=1;i<=B;i++)
        for(int j=1;j<=n;j++)
            a[i][j]=a[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1];
    for(int i=B+1;i<=n;i++)
        for(int j=1;j<=B;j++)
            b[i][j]=b[i][j]+b[i-1][j]+b[i][j-1]-b[i-1][j-1];
    for(int i=1,Xl,Yl,Xr,Yr;i<=q;i++){
        Xl=To[i-1]+1,Yl=Lo[i-1]+1,Xr=Bo[i-1]+1,Yr=Ro[i-1]+1;
        if(Xr<=B)Ans.push_back(Geta(Xl,Yl,Xr,Yr));
        else if(Xl>B&&Yr<=B)Ans.push_back(Getb(Xl,Yl,Xr,Yr));
        else if(Yr<=B)Ans.push_back(Getb(B+1,Yl,Xr,Yr)+Geta(Xl,Yl,B,Yr));
        else{
            int A=0;
            if(Xl<=B)A+=Geta(Xl,Yl,B,Yr),Xl=B+1;
            if(Yl<=B)A+=Getb(Xl,Yl,Xr,B),Yl=B+1;
            Ans.push_back(A+Solve(Xl,Yl,Xr,Yr));
        }
    }
    return Ans;
}

主函数部分是直接从题目附件里贺的：

#ifndef ONLINE_JUDGE
int main() {
  int N;
  assert(1 == scanf("%d", &N));
  std::vector<int> Xo(N), Yo(N);
  for (int i = 0; i < N; i++)
    assert(1 == scanf("%d", &Xo[i]));
  for (int i = 0; i < N; i++)
    assert(1 == scanf("%d", &Yo[i]));
  int Q;
  assert(1 == scanf("%d", &Q));
  std::vector<int> To(Q), Bo(Q), Lo(Q), Ro(Q);
  for (int k = 0; k < Q; k++)
    assert(4 == scanf("%d%d%d%d", &To[k], &Bo[k], &Lo[k], &Ro[k]));
  fclose(stdin);

  std::vector<long long> Co = mosaic(Xo, Yo, To, Bo, Lo, Ro);

  int S = (int)Co.size();
  for (int k = 0; k < S; k++)
    printf("%lld\n", Co[k]);
  fclose(stdout);

  return 0;
}
#endif