题解：CF1252K Addition Robot

CJ_Fu · 2025-02-11 20:02:05 · 题解

CF1252K Addition Robot

*2100

给一个 AB 串，定义函数 f(l,r,x,y)：

function f(L, R, x, y):
    for i from L to R
        if S[i] = 'A'
        x = x + y
        else
        y = x + y
    return (x, y)

考虑把 A/B 自身看做一个对二元组 (x,y) 的 transform，即 A((x,y))=(1x+1y,0x+1y),B((x,y))=(1x+0y,1x+1y)（方便书写后面省略最外层括号），我们要求的其实就是一系列变换的嵌套。由于嵌套后的结果仍关于 x,y 呈线性，所以考虑用线段树维护。

设左半区间得到的嵌套函数 F(x,y)=(ax+by,cx+dy)，右半为 G(x,y)=(ex+fy,gx+hy)，则 G(F(x,y))=(e(ax+by)+f(cx+dy),g(ax+by)+h(cx+dy))=((ae+cf)x+(be+df)y,(ag+ch)x+(bg+dh)y)，由此即可直接合并左右区间了，注意有顺序。（其实形式和矩阵乘法差不多）

再考虑取反操作，其实就是相当于把区间内所有 A,B 变换反转，由于线性性，直接反转区间变换后的系数（实现可以用 swap）并打上懒标记下传即可（实现可以用异或）。时间复杂度 O(n\log n)。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e5+7;
const int mod=1e9+7;
#define ls (now<<1)
#define rs (now<<1|1)
#define mid ((l+r)>>1)
char s[maxn];
int n,q;
struct seg{
    struct node{
        struct trans{
            int x,y;
            int q(int A,int B){return (x*A%mod+y*B%mod)%mod;}
        }a,b;
        node(){a.x=0;a.y=0;b.x=0;b.y=0;}
        node friend operator+(const node &a, const node &b){
            node c;
            c.a.x=(a.a.x*b.a.x%mod+a.b.x*b.a.y%mod)%mod;
            c.a.y=(a.a.y*b.a.x%mod+a.b.y*b.a.y%mod)%mod;
            c.b.x=(a.a.x*b.b.x%mod+a.b.x*b.b.y%mod)%mod;
            c.b.y=(a.a.y*b.b.x%mod+a.b.y*b.b.y%mod)%mod;
            return c;
        }
    }tr[maxn<<2];
    int tag[maxn<<2];
    void upd(node &x,node y){x=x+y;}
    void pushup(int now){tr[now]=tr[ls]+tr[rs];}
    void pushdown(int now,int l,int r){
        if(!tag[now]) return;
        tag[ls]^=tag[now];
        tag[rs]^=tag[now];
        swap(tr[ls].a,tr[ls].b);
        swap(tr[ls].a.x,tr[ls].a.y);
        swap(tr[ls].b.x,tr[ls].b.y);
        swap(tr[rs].a,tr[rs].b);
        swap(tr[rs].a.x,tr[rs].a.y);
        swap(tr[rs].b.x,tr[rs].b.y);
        tag[now]=0;
    }
    void build(int now,int l,int r){
        if(l==r){
            if(s[l]=='A') tr[now].a={1,1},tr[now].b={0,1};
            else tr[now].a={1,0},tr[now].b={1,1}; 
            return;
        }
        build(ls,l,mid); build(rs,mid+1,r);
        pushup(now);
    }
    void modify(int now,int l,int r,int L,int R){
        if(L<=l&&r<=R){
            tag[now]^=1;
            swap(tr[now].a,tr[now].b);
            swap(tr[now].a.x,tr[now].a.y);
            swap(tr[now].b.x,tr[now].b.y);
            return;
        }
        pushdown(now,l,r);
        if(L<=mid) modify(ls,l,mid,L,R);
        if(mid+1<=R) modify(rs,mid+1,r,L,R);
        pushup(now);
    }
    node query(int now,int l,int r,int L,int R){
        if(L<=l&&r<=R) return tr[now];
        pushdown(now,l,r);
        if(L<=mid&&mid+1<=R) return query(ls,l,mid,L,R)+query(rs,mid+1,r,L,R);
        if(L<=mid) return query(ls,l,mid,L,R);
        if(mid+1<=R) return query(rs,mid+1,r,L,R);
        return node();
    }
}t;
signed main(){
    cin>>n>>q;
    cin>>(s+1);
    t.build(1,1,n);
    for(int o=1,op,a,b,l,r;o<=q;o++){
        cin>>op;
        if(op&1){
            cin>>l>>r;
            t.modify(1,1,n,l,r);
        }else{
            cin>>l>>r>>a>>b;
            auto t1=t.query(1,1,n,l,r);
            cout<<t1.a.q(a,b)<<' '<<t1.b.q(a,b)<<'\n';
        }
    }
    return 0;
}