题解 P10061 [SNOI2024] 矩阵

· · 题解

VP 的时候想出来了，很开心！但是考试结束后 57 min 才过

该算法复杂度劣但常数小，当前最优解似乎也是该算法，现有题解未证明其复杂度，这里补一个。

发现旋转操作互相影响难以处理，尝试树形数据结构未果，发现操作间的互相影响并不太多，而且部分分中有 q 较小的数据但没有 n 较小的，考虑对操作分块。具体地，对于 B 次操作，它们的 2B 个 x 坐标最多将坐标轴划分为 2x+1 段，y 坐标同理，因此矩阵最多被划分成 (2x+1)^2 个子矩阵。注意这里的分析并不是将矩阵划分后旋转，而是每次询问时划分一下，这样最终就会被划分成上述最多(2x+1)^2 个子矩阵。

把询问分成大小为 B 的块，对于每次询问，暴力遍历目前所有 O(B^2) 个子矩阵并进行划分，然后暴力打标记，每 \frac{q}{B} 次询问后重构矩阵，复杂度为 O\left(\frac{q}{B}\left(B^3+n^2\right)\right)=O\left(qB^2+\frac{qn^2}{B}\right)，取 B=n^{\frac{2}{3}} 复杂度为 O(qn^{\frac{4}{3}})。实现时取 B=70 比较快。

代码较长，细节多。

#include<bits/stdc++.h>
using namespace std;
const int N=3003,p0=998244353,p1=1000000007,BLK=70,Q=19890;
int n,q,tp,ans,A[N][N],B[N][N];
struct node{int x,y,l1,l2,a,b,d,t;}st[Q];
int add(int x,int y){return x+y>=p1?x+y-p1:x+y;}
void rebuild(){
    for(int i=1;i<=tp;++i)
        if(st[i].d==0)
            for(int j=0;j<=st[i].l1;++j)
                for(int k=0;k<=st[i].l2;++k)
                    B[st[i].a+j][st[i].b+k]=add(A[st[i].x+j][st[i].y+k],st[i].t);
        else if(st[i].d==1)
            for(int j=0;j<=st[i].l1;++j)
                for(int k=0;k<=st[i].l2;++k)
                    B[st[i].a-k][st[i].b+j]=add(A[st[i].x+j][st[i].y+k],st[i].t);
        else if(st[i].d==2)
            for(int j=0;j<=st[i].l1;++j)
                for(int k=0;k<=st[i].l2;++k)
                    B[st[i].a-j][st[i].b-k]=add(A[st[i].x+j][st[i].y+k],st[i].t);
        else
            for(int j=0;j<=st[i].l1;++j)
                for(int k=0;k<=st[i].l2;++k)
                    B[st[i].a+k][st[i].b-j]=add(A[st[i].x+j][st[i].y+k],st[i].t);
    for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) A[i][j]=B[i][j];
    st[tp=1]={1,1,n-1,n-1,1,1,0,0};
}
void split1(int x){
    for(int i=tp;i;--i)
        if(st[i].d==0){
            if(st[i].a<=x&&x<st[i].a+st[i].l1){
                st[++tp]=st[i],st[i].l1=x-st[i].a;
                st[tp].l1-=x-st[i].a+1,st[tp].x+=x-st[i].a+1,st[tp].a=x+1;
            }
        }else if(st[i].d==1){
            if(st[i].a-st[i].l2<=x&&x<st[i].a){
                st[++tp]=st[i],st[i].l2=st[i].a-x-1;
                st[tp].l2-=st[i].a-x,st[tp].y+=st[i].a-x,st[tp].a=x;
            }
        }else if(st[i].d==2){
            if(st[i].a-st[i].l1<=x&&x<st[i].a){
                st[++tp]=st[i],st[i].l1=st[i].a-x-1;
                st[tp].l1-=st[i].a-x,st[tp].x+=st[i].a-x,st[tp].a=x;
            }
        }else{
            if(st[i].a<=x&&x<st[i].a+st[i].l2){
                st[++tp]=st[i],st[i].l2=x-st[i].a;
                st[tp].l2-=x-st[i].a+1,st[tp].y+=x-st[i].a+1,st[tp].a=x+1;
            }
        }
}
void split2(int x){
    for(int i=tp;i;--i)
        if(st[i].d==0){
            if(st[i].b<=x&&x<st[i].b+st[i].l2){
                st[++tp]=st[i],st[i].l2=x-st[i].b;
                st[tp].l2-=x-st[i].b+1,st[tp].y+=x-st[i].b+1,st[tp].b=x+1;
            }
        }else if(st[i].d==1){
            if(st[i].b<=x&&x<st[i].b+st[i].l1){
                st[++tp]=st[i],st[i].l1=x-st[i].b;
                st[tp].l1-=x-st[i].b+1,st[tp].x+=x-st[i].b+1,st[tp].b=x+1;
            }
        }else if(st[i].d==2){
            if(st[i].b-st[i].l2<=x&&x<st[i].b){
                st[++tp]=st[i],st[i].l2=st[i].b-x-1;
                st[tp].l2-=st[i].b-x,st[tp].y+=st[i].b-x,st[tp].b=x;
            }
        }else{
            if(st[i].b-st[i].l1<=x&&x<st[i].b){
                st[++tp]=st[i],st[i].l1=st[i].b-x-1;
                st[tp].l1-=st[i].b-x,st[tp].x+=st[i].b-x,st[tp].b=x;
            }
        }
}
int a,b,c,d;
bool chk(int i){
    if(st[i].d==0)
        return a<=st[i].a&&st[i].a+st[i].l1<=c&&b<=st[i].b&&st[i].b+st[i].l2<=d;
    if(st[i].d==1)
        return a<=st[i].a-st[i].l2&&st[i].a<=c&&b<=st[i].b&&st[i].b+st[i].l1<=d;
    if(st[i].d==2)
        return a<=st[i].a-st[i].l1&&st[i].a<=c&&b<=st[i].b-st[i].l2&&st[i].b<=d;
    if(st[i].d==3)
        return a<=st[i].a&&st[i].a+st[i].l2<=c&&b<=st[i].b-st[i].l1&&st[i].b<=d;
    return 0;
}
int main(){
    scanf("%d%d",&n,&q),st[tp=1]={1,1,n-1,n-1,1,1,0,0};
    for(int i=1;i<=n;++i)
        for(int j=1,c=1;j<=n;++j)
            A[i][j]=c=c*1ll*(i+1)%p0;
    for(int _=1,op;_<=q;++_){
        scanf("%d%d%d%d%d",&op,&a,&b,&c,&d);
        split1(c),split1(a-1),split2(d),split2(b-1);
        if(op==1){
            op=c-a+1;
            for(int i=tp,x,y;i;--i)
                if(chk(i)){
                    st[i].d=(st[i].d+1)&3;
                    x=op-st[i].b+b,y=st[i].a-a+1;
                    st[i].a=a+x-1,st[i].b=b+y-1;
                }
        }else{
            scanf("%d",&op);
            for(int i=tp;i;--i)
                if(chk(i))
                    st[i].t=add(st[i].t,op);
        }
        if(_==q||_%BLK==0) rebuild();
    }
    for(int i=1,s=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            s=s*12345ll%p1,ans=(ans+A[i][j]*1ll*s)%p1;
    return printf("%d",ans),0;
}