一道神秘的数据结构题。

题目链接。

题意

给定一个 $n\times n$ 的矩阵，共有 $q$ 次操作，分为两种：

1. 给定一个正方形区域，将其逆时针旋转；
2. 给定一个矩形区域，同时加一个值。

时限 $8s$。

$1\le n,q\le 3000$。

题解

发现时限非常大，而 $n\times q$ 却只有 $9\times 10^6$。

普通的思路是，拿两棵平衡树分别维护矩阵的行与列。

矩阵加直接做，旋转可以把平衡树裂开，打反转标记，然后和另一棵平衡树合并在一起（横向的合并去竖向的，竖向的合并去横向的）。

时间复杂度是 $O(n^2+nq\log n)$，看起来很对？

经过一些了解，在考场上这么写的人，大部分在本地跑到了 $100s\sim 250s$（包括我）。

下面是正解：

经过上面平衡树的尝试，我们完全可以知道，这道题维护的复杂度常数一定是巨大的。

这也就告诉我们，正解大概率是单次询问 $O(n)$ 的做法。

发现一个问题，假如只有矩阵加操作，这道题是好做的。

那么说明这道题的难点应该在于旋转操作。

考虑这么一件事情，如果保证旋转操作的对象一直是整个矩阵，这道题好做吗？

非常好做，我们只需要额外维护，整个矩阵现在被操作了几次就好了。

为什么只需要这样就可以维护整个矩阵呢？

因为在旋转的过程中，矩阵内部的“结构”是相对不变的，原来相邻的两个位置现在还是相邻。

这就是旋转操作的特点，回到原题，这告诉我们，假如去维护元素之间的相对位置，那么每一次旋转操作只有 $O(n)$ 个地方会被改变。

那么什么数据结构维护了一个矩阵中，元素之间的相对位置呢？答案是十字链表。

好，现在我们已经知道了旋转操作可以使用十字链表进行维护，那么矩阵加操作也很简单了。

单次 $O(1)$ 的矩阵加操作是困难的，但是单次 $O(n)$ 是简单的，我们只需要维护元素相对位置的同时，维护一下他们两个的差就好了。

做法总结：

1. 使用十字链表维护，每一个元素周围四个位置是谁，他们的差是多少；
2. 对于旋转操作，暴力找到需要断开的位置，然后旋转，再拼上，单次复杂度 $O(n)$；
3. 对于矩阵加操作，差变化的位置也只有 $O(n)$ 个，暴力找到位置，修改，单次复杂度 $O(n)$。

下面是几个实现细节：

1. 对于两种操作，都有 $O(n)$ 个位置需要修改，而链表不支持随机访问，复杂度为什么还是 $O(n)$ 的？

   可以发现，每一次需要修改的地方，一定是 $8$ 条（或者 $4$ 条）连续的线段，这些位置我们可以在 $O(n)$ 的时间内一起找到。

2. 假如我们维护每一个位置，左右上下分别是哪些元素，那么在一次旋转过后，他们的方向会改变，这怎么维护？

   这是一个好问题，我暂时没有想到很好的解决方案。

   我的代码只是维护了四个位置的相对顺序，并没有强制钦定哪一个位置对应哪一个方向，访问的时候我们其实可以直接算出这个元素被旋转了几次。

总复杂度 $O(n^2+nq)$。

代码

跑了 $7s$，常数确实大。

代码

感谢观看！

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
    int s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
const int mod=1000000007;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
struct node
{
    node *f[4];//4个方向分别是哪个点
    ll d[4];//4个方向差分数组
    int id[4];//4个方向,目标点的方向
}a[10000001];
struct V
{
    node *f;
    ll val;
    int d;
}v1[3001],v2[3001],v3[3001],v4[3001],v5[3001],v6[3001],v7[3001],v8[3001];
int id[3001][3001];
ll s[3001][3001];
int n,m;
inline void init()
{
    for(int i=1;i<=n;i++)
    {
        ll now=1;
        for(int j=1;j<=n;j++) s[i][j]=now=now*(i+1)%998244353;
    }
    for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) id[i][j]=i*(n+1)+j+1;
    for(int i=0;i<=n;i++) for(int j=0;j<=n;j++)
    {
        node *f=a+id[i][j];
        for(int p=0;p<4;p++)
        {
            int x=(i+dx[p]+n+1)%(n+1),y=(j+dy[p]+n+1)%(n+1);
            f->f[p]=a+id[x][y];
            f->d[p]=s[x][y]-s[i][j];
            f->id[p]=p;
        }
    }
}
inline void run(node *&f,int &d,ll &now,int op)
{
    int num=(op+d)%4;
    now+=f->d[num];
    d=(f->id[num]-op+4)%4;
    f=f->f[num];
}
//把第i行薅出来
inline void geth(int i,V *v)
{
    node *f=a+1;int d=0;ll now=0;
    for(int j=1;j<=i;j++) run(f,d,now,1);
    for(int j=1;j<=n;j++)
    {
        run(f,d,now,0);
        v[j].f=f,v[j].val=now,v[j].d=d;
    }
}
//把第i列薅出来
inline void getw(int i,V *v)
{
    node *f=a+1;int d=0;ll now=0;
    for(int j=1;j<=i;j++) run(f,d,now,0);
    for(int j=1;j<=n;j++)
    {
        run(f,d,now,1);
        v[j].f=f,v[j].val=now,v[j].d=d;
    }
}
inline void geth(int i,V *v1,V *v2,int l,int r)
{
    geth(i,v1);
    for(int j=l;j<=r;j++)
    {
        v2[j]=v1[j];
        run(v2[j].f,v2[j].d,v2[j].val,1);
    }
}
inline void getw(int i,V *v1,V *v2,int l,int r)
{
    getw(i,v1);
    for(int j=l;j<=r;j++)
    {
        v2[j]=v1[j];
        run(v2[j].f,v2[j].d,v2[j].val,0);
    }
}
inline void output()
{
    ll now=1,ans=0;
    for(int i=1;i<=n;i++)
    {
        geth(i,v1);
        for(int j=1;j<=n;j++)
        {
            now=now*12345%mod;
            ans=(ans+v1[j].val%mod*now)%mod;
        }
    }
    printf("%lld\n",ans);
}
inline void change(node *f1,node *f2,ll v1,ll v2,int d1,int d2,int op)
{
    // f1 --op-> f2
    int num1=(op+d1)%4,num2=(op+2+d2)%4;
    f1->f[num1]=f2;
    f1->d[num1]=v2-v1;
    f1->id[num1]=(num2+2)%4;
    f2->f[num2]=f1;
    f2->d[num2]=v1-v2;
    f2->id[num2]=(num1+2)%4;
}
inline void link(V &v1,V &v2,int d1,int d2,int op)
{
    change(v1.f,v2.f,v1.val+d1,v2.val,(v1.d+d2)%4,v2.d,op);
}
inline void add(int xl,int yl,int xr,int yr,int d)
{
    getw(yl-1,v7,v3,xl,xr);
    getw(yr,v1,v5,xl,xr);
    geth(xl-1,v8,v4,yl,yr);
    geth(xr,v2,v6,yl,yr);
    for(int i=xl;i<=xr;i++) link(v1[i],v5[i],d,0,0);
    for(int i=yl;i<=yr;i++) link(v2[i],v6[i],d,0,1);
    for(int i=xl;i<=xr;i++) link(v3[i],v7[i],d,0,2);
    for(int i=yl;i<=yr;i++) link(v4[i],v8[i],d,0,3);
}
inline void rotate(int xl,int yl,int xr,int yr)
{
    getw(yl-1,v7,v3,xl,xr);
    getw(yr,v1,v5,xl,xr);
    geth(xl-1,v8,v4,yl,yr);
    geth(xr,v2,v6,yl,yr);
    for(int i=xl;i<=xr;i++) link(v2[yr-i+xl],v5[i],0,1,0);
    for(int i=yl;i<=yr;i++) link(v3[xl+i-yl],v6[i],0,1,1);
    for(int i=xl;i<=xr;i++) link(v4[yr-i+xl],v7[i],0,1,2);
    for(int i=yl;i<=yr;i++) link(v1[xl+i-yl],v8[i],0,1,3);
}
int main()
{
    n=read(),m=read(),init();
    for(int i=1;i<=m;i++)
    {
        int op=read(),xl=read(),yl=read(),xr=read(),yr=read();
        if(op==1) rotate(xl,yl,xr,yr);
        else add(xl,yl,xr,yr,read());
    }
    output();
    return 0;
}