题面

记忆犹新

题解

f 函数值给得非常明显，一看就给人一种熟悉感——这不是连分数吗？

众所周知，连分数有个递推公式，即

−

p_i=a_ip_{i-1}+p_{i-2}\\ q_i=a_iq_{i-1}+q_{i-2}

pi=aipi−1+pi−2qi=aiqi−1+qi−2

而且不用管约分，因为根据这个式子算出来的一定是最简分数。

可以发现两者的转移式子几乎一模一样，只是初值不同。

于是，一种方式是用矩阵维护转移，分子分母的转移式子相同，只用存一份。

这样就可以解决只有 APPEND 操作的数据了。

但是我们发现，如果把转移跟

a 序列绑定在一起，很不好搞。我们其实可以把转移和操作序列绑定：

我们把向量矩阵定义为

(

−

)

(p_i,p_{i-1},p_{i-2})

(pi,pi−1,pi−2) 和

(

−

)

(q_i,q_{i-1},q_{i-2})

(qi,qi−1,qi−2) ，我们不妨从

p 入手，翻译操作类型代表的矩阵，

W 类型：最后一个+1，也就是

p

i
- ⁣ ⁣
=

p

i

−

1

p_i+\!\!=p_{i-1}

pi+=pi−1 ，这个可以转化为矩阵

(

1

0

0

1

1

0

0

0

1

)

\left(\begin{matrix}1&0&0\\1&1&0\\0&0&1\end{matrix}\right)

⎝⎛110010001⎠⎞ 。

E 类型，分两种小情况：

WE：前面是个 W ，保证了

a

a

a 序列最后一个元素大于 1，那么把它减 1，再添两个 1，此时的 E 的转移矩阵为

(

2

1

1

−

1

0

−

1

0

0

0

)

\left(\begin{matrix}2&1&1\\-1&0&-1\\0&0&0\end{matrix}\right)

⎝⎛2−101001−10⎠⎞ 。
_E：除了前面是 W 之外的情况，容易发现

a

a

a 序列最后一个元素必定为 1，那么把倒数第二个数+1，此时比较麻烦，要牵扯到

p

i

−

2

p_{i-2}

pi−2 ，这也是我定义

3

×

3

3\times3

3×3 矩阵的原因。从递推公式上算，转移矩阵应该是

(

1

0

0

0

1

0

1

1

1

)

\left(\begin{matrix}1&0&0\\0&1&0\\1&1&1\end{matrix}\right)

⎝⎛101011001⎠⎞ 。

为了方便，我们算出

(

−

)

(

−

)

(

)

{\tt WE}:\left(\begin{matrix}2&1&1\\-1&0&-1\\0&0&0\end{matrix}\right)={\tt X}:\left(\begin{matrix}1&0&1\\0&1&-1\\0&0&0\end{matrix}\right)\times{\tt\_E}:\left(\begin{matrix}1&0&0\\0&1&0\\1&1&1\end{matrix}\right)

WE:⎝⎛2−101001−10⎠⎞=X:⎝⎛1000101−10⎠⎞×_E:⎝⎛101011001⎠⎞ ，用这个

{\tt X}

X 矩阵进行 WE 的计算，那么相当于所有的 E 都先看成是 _E 类型，然后若出现了 WE ，就在 W 和 E 中间乘上矩阵

\tt X

X 。

现在，该有的推理都已经结束了，开始我们的平衡树之旅了。

平衡树中要记录两个 char 表示左右端点的字符，四个矩阵，分别记录无颜色翻转无旋转，无颜色翻转有旋转，有颜色翻转无旋转，有颜色翻转有旋转这四种情况下的区间转移矩阵，还有懒标记，以及平衡树必有的 son，siz，和随机值。

CODE

为了使

3\times3

3×3 的矩阵过掉，卡常数颇费心思。

#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 100005
#define ENDL putchar('\n')
#define LL long long
#define DB double
#define lowbit(x) ((-x) & (x))
LL read() {
    LL f = 1,x = 0;char s = getchar();
    while(s < '0' || s > '9') {if(s=='-')f = -f;s = getchar();}
    while(s >= '0' && s <= '9') {x=x*10+(s-'0');s = getchar();}
    return f * x;
}
void putint(int x) {
    if(!x) return ;
    putint(x/10);putchar(x%10+'0');
    return ;
}
const int MOD = 998244353;
int n,m,i,j,s,o,k;
int Q,X = 123127;
int my_rand() {
    return X = (X *2333ll + 2344243ll) % MOD;
}
char ss[MAXN<<1];
struct mat{
    int n,m;
    int s[3][3];
    mat(){n=m=0;}
    mat(int x) {n=m=3;memset(s,0,sizeof(s));for(int i = 0;i < 3;i ++)s[i][i]=x;}
    void set(int N,int M) {n=N;m=M;memset(s,0,sizeof(s));}
}Ap,Aq,W,WE,_E,nm1;
void MD(int &x) {if(x>=MOD)x-=MOD;}
// p_-2 = 0, p_-1 = 1; q_-2 = 1, q_-1 = 0;
mat operator * (mat a,mat b) {
    mat c;c.n = a.n;c.m = b.m;
    c.s[0][0] = (a.s[0][0]*1ll*b.s[0][0]+a.s[0][1]*1ll*b.s[1][0]+a.s[0][2]*1ll*b.s[2][0]) % MOD;
    c.s[0][1] = (a.s[0][0]*1ll*b.s[0][1]+a.s[0][1]*1ll*b.s[1][1]+a.s[0][2]*1ll*b.s[2][1]) % MOD;
    c.s[0][2] = (a.s[0][0]*1ll*b.s[0][2]+a.s[0][1]*1ll*b.s[1][2]+a.s[0][2]*1ll*b.s[2][2]) % MOD;

    c.s[1][0] = (a.s[1][0]*1ll*b.s[0][0]+a.s[1][1]*1ll*b.s[1][0]+a.s[1][2]*1ll*b.s[2][0]) % MOD;
    c.s[1][1] = (a.s[1][0]*1ll*b.s[0][1]+a.s[1][1]*1ll*b.s[1][1]+a.s[1][2]*1ll*b.s[2][1]) % MOD;
    c.s[1][2] = (a.s[1][0]*1ll*b.s[0][2]+a.s[1][1]*1ll*b.s[1][2]+a.s[1][2]*1ll*b.s[2][2]) % MOD;

    c.s[2][0] = (a.s[2][0]*1ll*b.s[0][0]+a.s[2][1]*1ll*b.s[1][0]+a.s[2][2]*1ll*b.s[2][0]) % MOD;
    c.s[2][1] = (a.s[2][0]*1ll*b.s[0][1]+a.s[2][1]*1ll*b.s[1][1]+a.s[2][2]*1ll*b.s[2][1]) % MOD;
    c.s[2][2] = (a.s[2][0]*1ll*b.s[0][2]+a.s[2][1]*1ll*b.s[1][2]+a.s[2][2]*1ll*b.s[2][2]) % MOD;
    return c;
}
struct it{
    char L,R;char f1,f2;
    mat m[2][2];
    it() {L=R=0;f1=f2=0;}
    it(int x){f1=f2=0;m[0][0]=m[0][1]=m[1][0]=m[1][1]=mat(1);f1=f2=0;}
    void flip() {
        if(L=='E') L='W'; else L='E';
        if(R=='E') R='W'; else R='E';
        f1 ^= 1;
    }
    void reverse() {
        swap(L,R);f2 ^= 1;
    }
}tre[(MAXN*2)<<2]={it(1)},nmb[(MAXN*2)<<2]={it(1)};
it merg(it a,it b) {
    if(!a.L) return b; if(!b.L) return a;
    it c;c.L = a.L;c.R = b.R;
    if(a.R=='W'&&b.L=='E') c.m[0][0] = a.m[a.f1][a.f2]*WE*b.m[b.f1][b.f2],c.m[1][1] = b.m[1^b.f1][1^b.f2]*WE*a.m[1^a.f1][1^a.f2];
    else c.m[0][0] = a.m[a.f1][a.f2]*b.m[b.f1][b.f2],c.m[1][1] = b.m[1^b.f1][1^b.f2]*a.m[1^a.f1][1^a.f2];

    if(a.R=='E'&&b.L=='W') c.m[0][1] = b.m[b.f1][1^b.f2]*WE*a.m[a.f1][1^a.f2],c.m[1][0] = a.m[1^a.f1][a.f2]*WE*b.m[1^b.f1][b.f2];
    else c.m[0][1] = b.m[b.f1][1^b.f2]*a.m[a.f1][1^a.f2],c.m[1][0] = a.m[1^a.f1][a.f2]*b.m[1^b.f1][b.f2];
    return c;
}
bool lz[(MAXN*2)<<2][2];
int sn[(MAXN*2)<<2][2],siz[(MAXN*2)<<2],hp[(MAXN*2)<<2],CNT;
// -----------------------------------------Treap!!!
struct np{
    int s[2];np(){s[0]=s[1]=0;}
};
int update(int x) {
    int ls = sn[x][0],rs = sn[x][1];
    siz[x] = siz[ls] + siz[rs] + 1;
    tre[x] = merg(tre[ls],merg(nmb[x],tre[rs]));
    return x;
}
void pushdown(int a) {
    int ls = sn[a][0],rs = sn[a][1];
    if(lz[a][0]) {
        tre[ls].flip(); tre[rs].flip();
        nmb[ls].flip(); nmb[rs].flip();
        lz[ls][0] ^= 1; lz[rs][0] ^= 1;
        lz[a][0] = 0;
    }
    if(lz[a][1]) {
        tre[ls].reverse(); tre[rs].reverse();
        nmb[ls].reverse(); nmb[rs].reverse();
        swap(sn[ls][0],sn[ls][1]); swap(sn[rs][0],sn[rs][1]);
        lz[ls][1] ^= 1; lz[rs][1] ^= 1;
        lz[a][1] = 0;
    }return ;
}
int maketree(char C) {
    int a = ++ CNT;
    lz[a][0] = lz[a][1] = 0;
    sn[a][0] = sn[a][1] = 0;
    hp[a] = my_rand();
    mat nw,nw2;
    if(C == 'W') nw = W,nw2 = _E;
    else nw = _E,nw2 = W;
    tre[a].L = tre[a].R = C;
    tre[a].m[0][0]=tre[a].m[0][1]=nw;
    tre[a].m[1][0]=tre[a].m[1][1]=nw2;
    nmb[a] = tre[a]; siz[a] = 1;
    return a;
}
np Split(int x,int rk) {
    np as = np();
    if(!x) return as;
    pushdown(x);
    int d = (siz[sn[x][0]]+1 <= rk);
    if(d) rk -= siz[sn[x][0]]+1;
    as = Split(sn[x][d],rk);
    sn[x][d] = as.s[d^1];
    as.s[d^1] = update(x);
    return as;
}
int Merge(int p1,int p2) {
    if(!p1 || !p2) return p1+p2;
    pushdown(p1); pushdown(p2);
    if(hp[p1] < hp[p2]) {
        sn[p1][1] = Merge(sn[p1][1],p2);
        return update(p1);
    }
    sn[p2][0] = Merge(p1,sn[p2][0]);
    return update(p2);
}
int Flip(int x,int l,int r) {
    np p2 = Split(x,r);
    np p1 = Split(p2.s[0],l-1);
    int a = p1.s[1];
    tre[a].flip();nmb[a].flip();
    lz[a][0] ^= 1;
    return Merge(Merge(p1.s[0],p1.s[1]),p2.s[1]);
}
int Reverse(int x,int l,int r) {
    np p2 = Split(x,r);
    np p1 = Split(p2.s[0],l-1);
    int a = p1.s[1];
    tre[a].reverse();nmb[a].reverse();
    lz[a][1] ^= 1; swap(sn[a][0],sn[a][1]);
    return Merge(Merge(p1.s[0],p1.s[1]),p2.s[1]);
}
//---------------------------------------Treap Forever!!!
int root = 0;
int main() {
    nm1 = mat(1);
    Ap.set(1,3); Aq.set(1,3);
    W.set(3,3); WE.set(3,3); _E.set(3,3);
    // p-1= 1, q-1= 0
    // p0 = 0, q0 = 1;
    // p1 = 1, q1 = 1;
    Ap.s[0][0] = 1; Ap.s[0][1] = 0; Ap.s[0][2] = 1;
    Aq.s[0][0] = 1; Aq.s[0][1] = 1; Aq.s[0][2] = 0;

    int tm1[3][3] = {{1,0,0},{1,1,0},{0,0,1}};
    memcpy(W.s,tm1,sizeof(W.s));

    int tm2[3][3] = {{1,0,1},{0,1,MOD-1},{0,0,0}};
    memcpy(WE.s,tm2,sizeof(WE.s));

    int tm3[3][3] = {{1,0,0},{0,1,0},{1,1,1}};
    memcpy(_E.s,tm3,sizeof(_E.s));

    n = read();Q = read();
    scanf("%s",ss + 1);
    for(int j = 1;j <= n;j ++) {
        root = Merge(root,maketree(ss[j]));
    }

    it as = tre[root];
    mat sp = Ap*as.m[as.f1][as.f2],sq = Aq*as.m[as.f1][as.f2];
    putint(sp.s[0][0]);putchar(' ');putint(sq.s[0][0]);ENDL;
    while(Q --) {
        char tps[15],cc;
        scanf("%s",tps);
        if(tps[0] == 'A') {
            cc = getchar();
            while(cc == ' ') cc = getchar();
            n ++;
            root = Merge(root,maketree(cc));
        }
        else if(tps[0] == 'F') {
            s = read();o = read();
            root = Flip(root,s,o);
        }
        else {
            s = read();o = read();
            root = Reverse(root,s,o);
        }
        it as = tre[root];
        mat sp = Ap*as.m[as.f1][as.f2],sq = Aq*as.m[as.f1][as.f2];
        putint(sp.s[0][0]);putchar(' ');putint(sq.s[0][0]);ENDL;
    }
    return 0;
}

过掉以后，发现由于序列特殊性，连分数其实可以用 2×2 的矩阵。