Wuyanru's blog
0%

[SNOI2024] 矩阵

发表于 分类于 ，

好气人，一道神秘的数据结构题。

题目链接。

题意

给定一个 的矩阵，共有 次操作，分为两种：

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

。

时限 。

题解

发现时限非常大，而 却只有 。

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

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

时间复杂度是 ，看起来很对？

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

下面是正解：

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

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

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

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

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

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

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

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

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

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

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

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

做法总结：

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

下面是几个实现细节：

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

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

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

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

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

总复杂度 。

代码

跑了 ，常数确实大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
#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;
}

感谢观看！