Codeforces 1252K Addition Robot 题解

发表于 | 阅读次数：
本文字数： 1.2k 字 | 阅读时长 ≈ 6 分钟

题意简述

你有一个字符串，仅由 A,B 两种字符构成。长度 $n\le 10^5$。维护 $Q$ 次操作，格式为：
1 L R 区间 $[L,R]$ 中，$A$ 变成 $B$，$B$ 变成 $A$。
2 L R A B 你有两个数，初始是 $A$ 和 $B$。从 $L$ 遍历到 $R$ ，如果这一位是字符 A，那么 $A=A+B$，否则 $B=A+B$，输出最后 $A$ 和 $B$ 变成什么样。

思路

线段树区间维护矩阵积，然后用 $[A,B]$ 左乘这个矩阵积，就能得到最后的 $A,B$。

关于交换操作：我们维护矩阵积的时候，维护取反后的矩阵积 （就是把 $A$ 变成 $B$ ，把 $B$ 变成 $A$ 后的矩阵积）。交换的时候，把两个矩阵积换一下，然后下传标记即可。

代码

点击
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
208
209
210
211
212
#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
    #define N 155555
    #define mod 1000000007
    #define F(i,l,r) for(int i=l;i<=r;++i)
    #define D(i,r,l) for(int i=r;i>=l;--i)
    #define Fs(i,l,r,c) for(int i=l;i<=r;c)
    #define Ds(i,r,l,c) for(int i=r;i>=l;c)
    #define MEM(x,a) memset(x,a,sizeof(x))
    #define FK(x) MEM(x,0)
    #define Tra(i,u) for(int i=G.Start(u),v=G.To(i);~i;i=G.Next(i),v=G.To(i))
    #define p_b push_back
    #define sz(a) ((int)a.size())
    #define iter(a,p) (a.begin()+p)
    void R1(int &x)
    {
        x=0;char c=getchar();int f=1;
        while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
        while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
        x=(f==1)?x:-x;
    }
    void Rd(int cnt,...)
    {
        va_list args;
        va_start(args,cnt);
        F(i,1,cnt) 
        {
            int* x=va_arg(args,int*);R1(*x);
        }
        va_end(args);
    }
    class Matrix //矩阵
    {
    #define S 5
    private:
        int a[S][S];
    public:
        int n;
        Matrix()
        {
            memset(a,0,sizeof(a));
            n=0;
        }
        Matrix(int _n)
        {
            memset(a,0,sizeof(a));
            n=_n;
        }
        Matrix(int _n,int _x)
        {
            n=_n;
            for(int i=0;i<S;++i)
            {
                for(int j=0;j<S;++j)
                {
                    a[i][j]=_x;
                }
            }
        }

        int* operator[](int i)
        {
            return *(a+i);
        }

        void Identity()
        {
            memset(a,0,sizeof(a));
            for(int i=0;i<S;++i)
            {
                a[i][i]=1;
            }
        }
        #undef S //5
    }A(2,1),B(2,1),I(2,0); 
    // A: A=A+B 的变换矩阵
    // B: B=A+B 的变换矩阵
    // I: 单位矩阵
    Matrix operator*(Matrix x,Matrix y) //并不需要用到快速幂的操作,于是我没写
    {
        Matrix ans(x.n,0);
        int n=ans.n;
        for(int i=1;i<=n;++i)
        {
            for(int j=1;j<=n;++j)
            {
                if (x[i][j])
                {
                    for(int k=1;k<=n;++k)
                    {
                        ans[i][k]=(ans[i][k]+1ll*x[i][j]*y[j][k]%mod)%mod;
                    }
                }
            }
        }
        return ans;
    }
    char a[N];
    class SegmentTree
    {
    public:
        struct node{int l,r; bool c; Matrix w[2];}tree[N<<2];
        #define ls index<<1
        #define rs index<<1|1

        #define L tree[index].l
        #define R tree[index].r
        #define W tree[index].w
        #define C tree[index].c
        #define lL tree[ls].l
        #define lR tree[ls].r
        #define lW tree[ls].w
        #define lC tree[ls].c
        #define rL tree[rs].l
        #define rR tree[rs].r
        #define rW tree[rs].w
        #define rC tree[rs].c
        void Update(int index=1)
        {
            W[0]=lW[0]*rW[0];
            W[1]=lW[1]*rW[1];
        }
        void Build(int l,int r,int index=1)
        {
            L=l,R=r;
            if (l==r)
            {
                if (a[l]=='A') {W[0]=A; W[1]=B;} // W[0] 维护当前矩阵，W[1] 维护取反后的矩阵
                else           {W[0]=B; W[1]=A;} // 这个边界显然吧...
                return;
            }
            int mid=(l+r)>>1;
            Build(l,mid,ls); Build(mid+1,r,rs);
            Update(index);
        }
        void FlipOne(int index=1) {C^=1; swap(W[0],W[1]);} // 交换一下 W[0] 和 W[1]
        void PushDown(int index=1) //记得下传标记
        {
            if (C)
            {
                FlipOne(ls); FlipOne(rs);
                C=0;
            }
        }
        void Flip(int l,int r,int index=1) //区间反转
        {
            if (l>R or L>r) return;
            if (l<=L and R<=r) return FlipOne(index);
            PushDown(index);
            Flip(l,r,ls); Flip(l,r,rs);
            Update(index);
        }
        Matrix Query(int l,int r,int index=1) //注意：区间矩阵积返回的是一个矩阵
        {
            if (l>R or L>r) return I;
            if (l<=L and R<=r) return W[0];
            PushDown(index);
            return Query(l,r,ls)*Query(l,r,rs);
        }
    }T;

    int n,m;
    void Input()
    {
        Rd(2,&n,&m);
        scanf("%s",a+1);
        A[1][2]=0; B[2][1]=0; I.Identity();
        /*
        A=
        [1 0]
        [1 1]
        B=
        [1 1]
        [0 1]
        */
        T.Build(1,n);
    }
    void Soviet()
    {
        F(i,1,m)
        {
            int o;R1(o);
            if (o==1) {int l,r;Rd(2,&l,&r); T.Flip(l,r);}
            if (o==2) 
            {
                int l,r,a,b; Rd(4,&l,&r,&a,&b);
                a%=mod; b%=mod;
                Matrix Trans(2,0); Trans=T.Query(l,r); 
                // 转移纠正
                Matrix Init(2,0); Init[1][1]=a; Init[1][2]=b;
                // 初始矩阵就是 [A,B]
                Init=Init*Trans;
                printf("%d %d\n",Init[1][1],Init[1][2]);
            }
        }
    }

    #define Flan void
    Flan IsMyWife()
    {
        Input();
        Soviet();
    }
}
int main()
{
    Flandre_Scarlet::IsMyWife();
    getchar();getchar();
    return 0;
}
w