题解：CF1252K Addition Robot

CF1252K Addition Robot

*2100

给一个 AB 串，定义函数

f(l,r,x,y)

：

CPP

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)

Q

次操作：

对 $s[l,r]$ 取反；
求 $f(l,r,A,B)\bmod 10^9+7$ 。

n,Q\le 10^5

考虑把 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)

。

CPP

#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;
}

题解：CF1252K Addition Robot

文章操作

CF1252K Addition Robot

相关推荐

评论

题解：CF1252K Addition Robot