P10061 [SNOI2024] 矩阵

Genius_Star · 2024-02-22 22:49:54 · 题解

神仙小清新数据结构题，膜拜……

思路：

刚开始想的是平衡树做法，维护每行每列的平衡树，时间复杂度为 O(QN \log N)，但是写了一大坨交上去获得了与暴力同分的“好成绩”，于是只能想正解。

这题总共写了两天，一天平衡树，一天写正解，调到大脑崩溃啊！

因为此题的难点是旋转操作，如果只有加法操作，可以用二维差分解决；但是加上懒标记后，这个差分标记无法一起旋转。

发现对于每次旋转后，矩阵内的点（即不在边界上的点）的相对位置是不会发生改变的，即这个点四周相邻的点是不会发生变化的；只有在边界上的点上下左右中有一个点会发生变化。

于是考虑对于每一个点维护一个十字链表，记录上下左右点的值与该点的差，这样只要知道矩阵中任意一个点的值，就可以由此推出整个矩阵的值。

对于每次操作：

• 将 x_1-1，x_1，x_2，x_2+1 这些行中 [y_1,y_2] 范围内的数提取出来；将 y_1，y_1，y_2，y_2+1 这些列中 [x_1,x_2] 范围内的数提取出来（因为这些位置所维护的十字链表会因为某些操作进行修改）。

但是因为有旋转操作，所以我们需要有一个源点 (0,0)，连接着 (0,1) 和 (1,0)，然后提取操作如下：

• 每次提取第 x 行 [l,r] 范围时，将源点往下走 x 次，走到 (x,0) 这个位置，然后向右走 l-1 次，走到 (x,l-1)；然后再走 r-l+1 次，每次将当前位置的节点记录下来。

• 每次提取第 x 列 [l,r] 范围时，将源点往右走 x 次，走到 (0,x) 这个位置，然后向下走 l-1 次，走到 (l-1,x)；然后再走 r-l+1 次，每次将当前位置的节点记录下来。

注意，在提取的时候，我们可以顺带将提取的节点的值给算出来，可以方便以后更新差值。

对于加法操作：

• 将上下左右的差进行更新即可。

对于旋转操作：

• 每次需要将边界上的点中其中一条边撤销，连向旋转后的另外一个点，更新差值。

这样我们会发现一个问题，虽然每次进行旋转后矩阵中间节点的相对位置不会改变，但是进行旋转后，原来在上面的点会旋到左边，在左边的点会旋到下边，依次类推。

这样是无法固定找到向某个方向移动的点是通过哪条边相连的，于是考虑对于每一个点维护当前被旋转的次数，也可以用十字链表记录与四周的差值，那么这样就可以进行维护了。

时间复杂度为 O(QN)。

最慢的点跑了 6.29s，感觉还不错。

常数优化：

• 如果需要对 4 取模的话，可以用 &3。

• 每次将第 x_1-1 行提取出 [y_1,y_2] 后记为 A_0，则第 x_1 行的 [y_1,y_2] 是由 A_0 中每一个元素往下走一次形成的；对于列也一样。

• 尽量使用 int，少使用 long long。

完整代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const ll N=3030,M=4,mod=1e9+7,P=998244353,mul=12345ll;
namespace IN{
    #define getc() (p1==p2&&(p2=(p1=buf)+inbuf->sgetn(buf,21),p1==p2)?EOF:*p1++)
    char buf[21],*p1,*p2;
    template<typename T>inline bool read(T &x){
        static std::streambuf *inbuf=cin.rdbuf();
        x=0;
        bool f=1;
        char c=getc();
        while(c<'0'||c>'9'){
            if(c=='-')
              f=-1;
            c=getc();
        }
        while(c>='0'&&c<='9'){
            x=(x<<1)+(x<<3)+(c^48);
            c=getc();
        }
        return f;
    }
    template<typename T,typename ...Args>inline bool read(T& a,Args& ...args){
       return read(a)&&read(args...);
    }
    #undef getc
}
namespace OUT{
    template<typename T>inline void put(T x){
        static std::streambuf *outbuf=cout.rdbuf();
        static char s[21];
        static int top=0;
        if(x<0){
            outbuf->sputc('-');
            x=-x;
        }
        if(!x){
            outbuf->sputc('0');
            outbuf->sputc('\n');
            return;
        }
        while(x){
            s[++top]=x%10+'0';
            x/=10;
        }
        while(top){
            outbuf->sputc(s[top]);
            --top;
        }
        outbuf->sputc('\n');
    }
    inline void putc(const char ch){
        static std::streambuf *outbuf=cout.rdbuf();
        outbuf->sputc(ch);
    }
    inline void putstr(string s){
        for(register int i=0;i<s.length();i++) putc(s[i]);
    }
    template<typename T>inline void put(const char ch,T x){
        static std::streambuf *outbuf=cout.rdbuf();
        static char s[21];
        static int top = 0;
        if(x<0){
            outbuf->sputc('-');
            x=-x;
        }
        if(!x){
            outbuf->sputc('0');
            outbuf->sputc(ch);
            return;
        }
        while(x){
            s[++top]=x%10+'0';
            x/=10;
        }
        while(top){
            outbuf->sputc(s[top]);
            --top;
        }
        outbuf->sputc(ch);
    }
    template<typename T,typename ...Args> inline void put(T a,Args ...args){
        put(a);
        put(args...);
    }
    template<typename T,typename ...Args> inline void put(const char ch,T a,Args ...args){
        put(ch,a);
        put(ch,args...);
    }
}
using namespace IN;
using namespace OUT;
struct St{
    int x,y;
}root;
struct Node{
    St H[M]; // 上下左右四个点的位置 
    int data[M]; // 上下左右四个点的值与该点的值的差 
    int sum[M]; // 上下左右四个点的旋转次数与该点的旋转次数的差 
    int k; // 记录当前点旋转次数 
    ll x; // 记录当前点的值 
}a[N][N];
int n,q,op;
int sum=0,t=mul,v;
int ans[N][N];
int cnt[N];
St A[8][N];
int dx[]={-1,0,1,0},dy[]={0,-1,0,1};
inline void init(){
    for(register int i=0;i<8;i++)
      cnt[i]=0;
} 
inline int check(register int x){
    return x<0?x+4:x;
}
inline St Down(St x){ // 往下走 
    St ans;
    register int t=check(2-a[x.x][x.y].k);
    ans=a[x.x][x.y].H[t&3];
    a[ans.x][ans.y].x=(a[x.x][x.y].x+a[x.x][x.y].data[t&3])%mod;
    a[ans.x][ans.y].k=(a[x.x][x.y].k+a[x.x][x.y].sum[t&3])&3;
    return ans;
}
inline St Right(St x){ // 往右走 
    St ans;
    register int t=check(3-a[x.x][x.y].k);
//  cout<<t<<'\n';
    ans=a[x.x][x.y].H[t&3];
    a[ans.x][ans.y].x=a[x.x][x.y].x+a[x.x][x.y].data[t&3];
    a[ans.x][ans.y].k=(a[x.x][x.y].k+a[x.x][x.y].sum[t&3])&3;
    return ans; 
}
inline void getn(register int x,register int l,register int r,register int h){ // 提取 x 行 [l,r] 的值 
    St root={0,0};
    for(register int i=1;i<=x;i++)
      root=Down(root);  
    for(register int i=1;i<l;i++)
      root=Right(root); 
    for(register int i=l;i<=r;i++){
        root=Right(root);
        A[h][cnt[h]++]=root;
    }
}
inline void getm(register int x,register int l,register int r,register int h){ // 提取 x 列 [l,r] 的值 
    St root={0,0};
    for(register int i=1;i<=x;i++)
      root=Right(root);
    for(register int i=1;i<l;i++)
      root=Down(root);
    for(register int i=l;i<=r;i++){
        root=Down(root);
        A[h][cnt[h]++]=root;
    }
}
inline void get(register int x1,register int y1,register int x2,register int y2){
    getn(x1-1,y1,y2,0);
    for(int i=0;i<cnt[0];i++)
      A[1][cnt[1]++]=Down(A[0][i]);
    getn(x2,y1,y2,3);
    for(int i=0;i<cnt[3];i++)
      A[2][cnt[2]++]=Down(A[3][i]); 
    getm(y1-1,x1,x2,4);
    for(int i=0;i<cnt[4];i++)
      A[5][cnt[5]++]=Right(A[4][i]);
    getm(y2,x1,x2,7);
    for(int i=0;i<cnt[7];i++)
      A[6][cnt[6]++]=Right(A[7][i]);
//  for(register int i=0;i<8;i++){
//      for(register int j=0;j<(int)cnt[i];j++){
//          printf("[%lld,%lld,%lld]",A[i][j].x,A[i][j].y,a[A[i][j].x][A[i][j].y].k);
//          if(j!=cnt[i]-1)
//            putchar(',');
//      }
//      putchar('\n');
//  }
}
inline void rotate(register int x1,register int y1,register int x2,register int y2){ // 旋转 
    init();
    get(x1,y1,x2,y2);
    for(register int i=0;i<cnt[0];i++){
        register int X1=A[0][i].x,Y1=A[0][i].y;
        register int X2=A[7][i].x,Y2=A[7][i].y;
        a[X2][Y2].k++;
        a[X1][Y1].sum[check(2-a[X1][Y1].k)]=check(a[X2][Y2].k-a[X1][Y1].k);
        a[X2][Y2].sum[check(-a[X2][Y2].k)]=check(a[X1][Y1].k-a[X2][Y2].k);
//      cout<<a[X1][Y1].k<<' '<<a[X2][Y2].k<<'\n';
        a[X1][Y1].data[check(2-a[X1][Y1].k)]=(a[X2][Y2].x-a[X1][Y1].x+mod)%mod;
        a[X1][Y1].H[check(2-a[X1][Y1].k)]={X2,Y2};
        a[X2][Y2].data[check(-a[X2][Y2].k)]=(a[X1][Y1].x-a[X2][Y2].x+mod)%mod;
        a[X2][Y2].H[check(-a[X2][Y2].k)]={X1,Y1};
        a[X2][Y2].k--;
    }
    for(register int i=0;i<cnt[2];i++){
        register int X1=A[2][i].x,Y1=A[2][i].y;
        register int X2=A[5][i].x,Y2=A[5][i].y;
        a[X2][Y2].k++;
        a[X2][Y2].k&=3;
        a[X1][Y1].sum[check(-a[X1][Y1].k)]=check(a[X2][Y2].k-a[X1][Y1].k);
        a[X2][Y2].sum[check(2-a[X2][Y2].k)]=check(a[X1][Y1].k-a[X2][Y2].k);
//      cout<<a[X2][Y2].k<<' '<<a[X2][Y2].k<<'\n';
        a[X1][Y1].data[check(-a[X1][Y1].k)]=(a[X2][Y2].x-a[X1][Y1].x+mod)%mod;
        a[X1][Y1].H[check(-a[X1][Y1].k)]={X2,Y2};
        a[X2][Y2].data[check(2-a[X2][Y2].k)]=(a[X1][Y1].x-a[X2][Y2].x+mod)%mod;
        a[X2][Y2].H[check(2-a[X2][Y2].k)]={X1,Y1};
        a[X2][Y2].k--;
    }
    for(register int i=0;i<cnt[4];i++){
        register int X1=A[4][i].x,Y1=A[4][i].y;
        register int X2=A[1][cnt[4]-i-1].x,Y2=A[1][cnt[4]-i-1].y;
        a[X2][Y2].k++;
        a[X2][Y2].k&=3;
        a[X1][Y1].sum[check(3-a[X1][Y1].k)]=check(a[X2][Y2].k-a[X1][Y1].k);
        a[X2][Y2].sum[check(1-a[X2][Y2].k)]=check(a[X1][Y1].k-a[X2][Y2].k);
//      cout<<a[X1][Y1].k<<' '<<a[X2][Y2].k<<'\n';
        a[X1][Y1].data[check(3-a[X1][Y1].k)]=(a[X2][Y2].x-a[X1][Y1].x+mod)%mod;
        a[X1][Y1].H[check(3-a[X1][Y1].k)]={X2,Y2};
        a[X2][Y2].data[check(1-a[X2][Y2].k)]=(a[X1][Y1].x-a[X2][Y2].x+mod)%mod;
        a[X2][Y2].H[check(1-a[X2][Y2].k)]={X1,Y1};  
//      a[X2][Y2].k--;
    }
    for(register int i=0;i<cnt[6];i++){
        register int X1=A[6][i].x,Y1=A[6][i].y;
        register int X2=A[3][cnt[3]-i-1].x,Y2=A[3][cnt[3]-i-1].y;
        a[X2][Y2].k++;
        a[X2][Y2].k&=3;
        a[X1][Y1].sum[check(1-a[X1][Y1].k)]=check(a[X2][Y2].k-a[X1][Y1].k);
        a[X2][Y2].sum[check(3-a[X2][Y2].k)]=check(a[X1][Y1].k-a[X2][Y2].k);
//      cout<<a[X1][Y1].k<<' '<<a[X2][Y2].k<<'\n';
        a[X1][Y1].data[check(1-a[X1][Y1].k)]=(a[X2][Y2].x-a[X1][Y1].x+mod)%mod;
        a[X1][Y1].H[check(1-a[X1][Y1].k)]={X2,Y2};
        a[X2][Y2].data[check(3-a[X2][Y2].k)]=(a[X1][Y1].x-a[X2][Y2].x+mod)%mod;
        a[X2][Y2].H[check(3-a[X2][Y2].k)]={X1,Y1};  
        a[X2][Y2].k--;      
    }   
}
inline void add(register int x1,register int y1,register int x2,register int y2,register int t){ // 加法 
    St v;
    init();
    get(x1,y1,x2,y2);
    for(int i=0;i<cnt[0];i++){
        v=A[0][i];
        a[v.x][v.y].data[check(2-a[v.x][v.y].k)]=(a[v.x][v.y].data[check(2-a[v.x][v.y].k)]+t)%mod;
    }
    for(int i=0;i<cnt[1];i++){
        v=A[1][i];
        a[v.x][v.y].data[check(-a[v.x][v.y].k)]=(a[v.x][v.y].data[check(-a[v.x][v.y].k)]-t+mod)%mod;
    }
    for(int i=0;i<cnt[2];i++){
        v=A[2][i];
        a[v.x][v.y].data[check(-a[v.x][v.y].k)]=(a[v.x][v.y].data[check(-a[v.x][v.y].k)]+t)%mod;
    }
    for(int i=0;i<cnt[3];i++){
        v=A[3][i];
        a[v.x][v.y].data[check(2-a[v.x][v.y].k)]=(a[v.x][v.y].data[check(2-a[v.x][v.y].k)]-t+mod)%mod;  
    }
    for(int i=0;i<cnt[4];i++){
        v=A[4][i];
        a[v.x][v.y].data[check(3-a[v.x][v.y].k)]=(a[v.x][v.y].data[check(3-a[v.x][v.y].k)]+t)%mod;
    }
    for(int i=0;i<cnt[5];i++){
        v=A[5][i];
        a[v.x][v.y].data[check(1-a[v.x][v.y].k)]=(a[v.x][v.y].data[check(1-a[v.x][v.y].k)]-t+mod)%mod;  
    }
    for(int i=0;i<cnt[6];i++){
        v=A[6][i];
        a[v.x][v.y].data[check(1-a[v.x][v.y].k)]=(a[v.x][v.y].data[check(1-a[v.x][v.y].k)]+t)%mod;
    }
    for(int i=0;i<cnt[7];i++){
        v=A[7][i];
        a[v.x][v.y].data[check(3-a[v.x][v.y].k)]=(a[v.x][v.y].data[check(3-a[v.x][v.y].k)]-t+mod)%mod;
    }
}
inline void dfs(register int h,St x){
    St t;
    for(register int i=1;i<=n;i++){
        t=Right(x);
//      cout<<t.x<<' '<<t.y<<'\n';
        ans[h][i]=(1ll*ans[h][i-1]+a[x.x][x.y].data[check(3-a[x.x][x.y].k)]+mod)%mod;
        x=t;
    }
}
int main(){
    read(n),read(q);
    for(register int i=1;i<=n;i++){
        register int t=1;
        for(register int j=1;j<=n;j++){
            t=1ll*t*(i+1)%P;
            a[i][j].x=t;
        }
    }
    for(register int i=0;i<=n+1;i++)
      a[i][0].x=a[0][i].x=a[n+1][i].x=a[0][n+1].x=0;
    for(register int i=0;i<=n+1;i++){
        for(register int j=0;j<=n+1;j++){
            for(register int k=0;k<4;k++){
                register int zx=i+dx[k],zy=j+dy[k];
                a[i][j].sum[k]=0;
                if(zx<0||zx>(n+1)||zy<0||zy>(n+1)){
                    a[i][j].data[k]=0;
                    continue;
                }
                a[i][j].H[k]={zx,zy};
                a[i][j].data[k]=(a[zx][zy].x-a[i][j].x+mod)%mod;
            }
        }
    }
    while(q--){
        read(op);
        register int x1,y1,x2,y2;
        read(x1),read(y1),read(x2),read(y2);
        if(op==1){
            if(x1==x2&&y1==y2)
              continue;
            rotate(x1,y1,x2,y2);
        }
        else{
            read(v);
            add(x1,y1,x2,y2,v);
        }
    }
    for(register int i=1;i<=n;i++)
      dfs(i,{i,0});
    for(register int i=1;i<=n;i++){
        for(register int j=1;j<=n;j++){
            sum=(sum+(1ll*ans[i][j]*t)%mod)%mod;
            t=(1ll*t*mul)%mod;
//          cout<<ans[i][j]<<' ';
        }
//      cout<<'\n';
    }
    put(sum);
    return 0;
}