Wuyanru's blog
0%

[NOI2021] 密码箱

发表于 分类于 ，

老师留的几道题里第一个做了的，写篇题解纪念一下。

这道题主要想要写一下我做题的思路。

题目链接：luoguP7739。

首先我们可以注意到这道题不同寻常的地方：别的题目都是让我们维护序列，但是这道题却让我们维护操作序列。

似乎非常麻烦啊。

但是什么东西可以维护呢？矩阵！

再看一下题目中的操作：翻转、反转。

一眼就可以看出正解是平衡树维护矩阵。

这些思路大概是我读完题之后就知道的，比较明显。

知道了算法，其实我们只需要推出这些矩阵就可以了，这才是这道题的重点。

我们现在再来想一个问题：假如我们现在通过矩阵，维护了某一个序列的答案。

我们现在给这个序列后面添加一个数字，我们可以算出答案吗？

似乎不行，或者说起码没有特别简单的方法。

但是如果这个数字添加在了整个序列的前面，我们却很好维护。

假如说 的答案为 ，这个时候序列变成 ，答案显然会变成 。

那也就是： 所以我们得到了一些启发：序列倒着会比较好维护。

其实正着可能也差不多，但是我还是觉得倒着比较方便。

然后我们再来看题目中给的操作。

首先我们来看 W 操作。

将序列中最后一个值加一，因为我们倒着维护序列，所以就是整个序列第一个位置加一。

假设说这个地方原来的值是 ，那么这个地方对应的矩阵就是 。

我们现在要将这个地方的矩阵要变成 。

因为对于任何 ，这个变换都要成立，所以稍微手推一下，就可以发现： 接下来我们来推 E，你会发现似乎有点麻烦。不慌，我们直接推。

对于第一个数字不是 的情况，就是先把这个数字减一，然后在序列前面添上两个 。

所以我们先推一下如何给一个数字减一，感觉和上面差不多。 那么这个矩阵推出来就是： 然后再来推一下第一个数字是 的情况。不妨写一下原来的矩阵和变化后的矩阵。

假设原来第二个数是 （第一个数是 ）。

那么开头的两个矩阵长这个样子： 我们将第二个数字加上一： 前两项都是常数项，我们把它们乘起来。 我们肯定尽量想将他表示成对第一个数字的操作，所以我们把第一项拆开： 可以带进去的数字有点多，不好算。

就这么卡住了嘛？

看看上面？ 没错，E 操作直接用这一个矩阵就可以解决。

矩阵就这样推完了。

我们再来看题目中的这些操作。

操作一，直接在所有矩阵前添加一个数字。

操作三，直接整个区间翻转。

操作二，看起来不好搞，实际上和操作三一样，直接暴力维护没有转和转了之后这个区间长什么样子就行。

倍常数，建议实现的时候尽量常数写小一点。

代码：

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
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
#include<algorithm>
#include<cstring>
#include<random>
#include<cstdio>
#include<ctime>
using namespace std;
const int mod=998244353;
mt19937 _rand(time(0)^clock());
using ll=long long;
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;
}
template<const int n,const int m>
struct mat
{
    ll a[n][m];
    template<const int q>
    mat<n,q> operator * (mat<m,q>b)
    {
        mat<n,q>ans;
        memset(ans.a,0,sizeof(ans.a));
        for(int i=0;i<n;i++)
            for(int k=0;k<m;k++)
                for(int j=0;j<q;j++)
                    (ans.a[i][j]+=a[i][k]*b.a[k][j])%=mod;
        return ans;
    }
    inline void debug()
    {
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++) printf("%lld ",a[i][j]);
            printf("\n");
        }
        printf("\n");
    }
};
mat<2,2>num0[200001];
mat<2,2>num1[200001];
mat<2,2>num2[200001];
mat<2,2>num3[200001];
mat<2,2>val0[200001];
mat<2,2>val2[200001];
bool rev[200001];
bool fli[200001];
int pri[200001];
int siz[200001];
int ls[200001];
int rs[200001];
char in[100002];
int root;
int tot;
int n,m;
int Neww()
{
    tot++;
    pri[tot]=_rand(),siz[tot]=1;
    num0[tot].a[0][0]=num0[tot].a[0][1]=num0[tot].a[1][1]=1;
    num2[tot].a[0][0]=2,num2[tot].a[0][1]=-1,num2[tot].a[1][0]=1;
    val0[tot]=num1[tot]=num0[tot],val2[tot]=num3[tot]=num2[tot];
    return tot;
}
int Newe()
{
    tot++;
    pri[tot]=_rand(),siz[tot]=1;
    num0[tot].a[0][0]=2,num0[tot].a[0][1]=-1,num0[tot].a[1][0]=1;
    num2[tot].a[0][0]=num2[tot].a[0][1]=num2[tot].a[1][1]=1;
    val0[tot]=num1[tot]=num0[tot],val2[tot]=num3[tot]=num2[tot];
    return tot;
}
inline void push_down(int p)
{
    if(rev[p])
    {
        rev[p]^=1;
        rev[ls[p]]^=1,rev[rs[p]]^=1;
        swap(ls[p],rs[p]);
        swap(num0[p],num1[p]),swap(num2[p],num3[p]);
    }
    if(fli[p])
    {
        fli[p]^=1;
        fli[ls[p]]^=1,fli[rs[p]]^=1;
        swap(num0[p],num2[p]),swap(num1[p],num3[p]),swap(val0[p],val2[p]);
    }
}
inline void push_up(int p)
{
    if(ls[p]) push_down(ls[p]);
    if(rs[p]) push_down(rs[p]);
    num0[p]=num0[ls[p]]*val0[p]*num0[rs[p]];
    num2[p]=num2[ls[p]]*val2[p]*num2[rs[p]];
    num1[p]=num1[rs[p]]*val0[p]*num1[ls[p]];
    num3[p]=num3[rs[p]]*val2[p]*num3[ls[p]];
    siz[p]=siz[ls[p]]+siz[rs[p]]+1;
}
int merge(int u,int v)
{
    // printf("merge %d %d\n",u,v);
    if(!u||!v) return u|v;
    if(pri[u]>=pri[v])
    {
        push_down(u);
        rs[u]=merge(rs[u],v);
        push_up(u);
        return u;
    }
    else
    {
        push_down(v);
        ls[v]=merge(u,ls[v]);
        push_up(v);
        return v;
    }
}
void split(int p,int s,int &x,int &y)
{
    if(!p){ x=y=0;return ;}
    push_down(p);
    if(siz[ls[p]]>=s)
    {
        y=p;
        split(ls[p],s,x,ls[y]);
        push_up(y);
    }
    else
    {
        x=p;
        split(rs[p],s-siz[ls[p]]-1,rs[x],y);
        push_up(x);
    }
}
void print()
{
    push_down(root);
    printf("%lld %lld\n",(num0[root].a[0][0]+mod)%mod,(num0[root].a[0][0]+num0[root].a[0][1]+2*mod)%mod);
}
void debug()
{
    // printf("root=%d\n",root);
    // for(int i=1;i<=tot;i++)
    // {
    //     printf("%d : ls=%d rs=%d rev=%d fli=%d siz=%d ",i,ls[i],rs[i],rev[i],fli[i],siz[i]);
    //     printf("%2lld %2lld  %2lld %2lld  %2lld %2lld  %2lld %2lld  %2lld %2lld  %2lld %2lld\n",val0[i].a[0][0],val0[i].a[0][1],val2[i].a[0][0],val2[i].a[0][1],num0[i].a[0][0],num0[i].a[0][1],num1[i].a[0][0],num1[i].a[0][1],num2[i].a[0][0],num2[i].a[0][1],num3[i].a[0][0],num3[i].a[0][1]);
    //     printf("                                ");
    //     printf("%2lld %2lld  %2lld %2lld  %2lld %2lld  %2lld %2lld  %2lld %2lld  %2lld %2lld\n",val0[i].a[1][0],val0[i].a[1][1],val2[i].a[1][0],val2[i].a[1][1],num0[i].a[1][0],num0[i].a[1][1],num1[i].a[1][0],num1[i].a[1][1],num2[i].a[1][0],num2[i].a[1][1],num3[i].a[1][0],num3[i].a[1][1]);
    // }
    // printf("\n");
}
int main()
{
    n=read(),m=read();scanf("%s",in+1);
    num0[0].a[0][0]=num0[0].a[1][1]=1;
    num1[0]=num2[0]=num3[0]=num0[0];
    for(int i=1;i<=n;i++)
    {
        if(in[i]=='W') root=merge(Neww(),root);
        else root=merge(Newe(),root);
    }
    print();
    debug();
    for(int i=1;i<=m;i++)
    {
        scanf("%s",in+1);
        if(in[1]=='A')
        {
            scanf("%s",in+1);
            if(in[1]=='E') root=merge(Newe(),root);
            else root=merge(Neww(),root);
            n++;
        }
        else if(in[1]=='R')
        {
            int r=n-read()+1,l=n-read()+1;
            int x,y,z;
            split(root,r,y,z);
            split(y,l-1,x,y);
            rev[y]^=1;
            root=merge(merge(x,y),z);
        }
        else
        {
            int r=n-read()+1,l=n-read()+1;
            int x,y,z;
            split(root,r,y,z);
            split(y,l-1,x,y);
            // printf("l=%d r=%d x=%d y=%d z=%d\n",l,r,x,y,z);
            debug();
            fli[y]^=1;
            root=merge(merge(x,y),z);
        }
        print();
        debug();
    }
    return 0;
}
/*
2 2
WE
APPEND E
FLIP 1 2
*/

感谢观看！