石油大--Contest2022 - 2020年秋季组队训练赛第二场--17107 Problem K、Addition Robot（线段树）

题面：

题意：
给定一个仅由 $A,B$A,B 组成的字符串，支持两种操作。
（1） $1$1 $l$l $r$r，对 $[l,r]$[l,r] 区间的字符进行翻转处理，即 $A$A 变为 $B$B ， $B$B 变为 $A$A。
（2） $1$1 $l$l $r$r $a$a $b$b ，利用 $[l,r]$[l,r] 区间的字符对 $a,b$a,b 进行操作，如果 $s\left[i\right]=A$s[i]=A，那么 $a=a+b$a=a+b，如果 $s\left[i\right]=B$s[i]=B ，那么 $b=a+b$b=a+b，操作具有后效性，输出操作之后的 $a,b$a,b。

题解：
不考虑 $a,b$a,b 的具体值，只考虑 $a,b$a,b 的系数。
那么只有以下两种情况。

(a​b​)∗(11​01​)=(a+b​b​)

(a​b​)∗(10​11​)=(a​a+b​)

区间修改对应线段树上区间修改，查询的时候查询区间矩阵的乘积即可。

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<set>
#include<ctime>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
#define lc (cnt<<1)
#define rc (cnt<<1|1)
#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
#define fhead(x) for(int i=head[(x)];i;i=nt[i])
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;

const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const double alpha=0.75;
const int mod=1e9+7;
const double eps=1e-8;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=100100;
const int maxm=100100;
const int maxp=100100;
const int up=1100;

struct node
{
    ll a[3][3];
    node(){}
    node(int b,int c,int d,int e)
    {
        a[1][1]=b,a[1][2]=c;
        a[2][1]=d,a[2][2]=e;
    }
    void init(void)
    {
        memset(a,0,sizeof(a));
        a[1][1]=a[2][2]=1;
    }
};

node a=node(1,0,1,1),b=node(1,1,0,1);
node ans;


node operator * (const node &a,const node &b)
{
    node c;
    memset(c.a,0,sizeof(c.a));
    for(int i=1;i<=2;i++)
    {
        for(int j=1;j<=2;j++)
        {
            for(int k=1;k<=2;k++)
            {
                c.a[i][j]=(c.a[i][j]+a.a[i][k]*b.a[k][j])%mod;
            }
        }
    }
    return c;
}

struct tree
{
    int l,r;
    int laz;
    node ans1,ans2;
}t[maxn<<2];

char str[maxn];

void pushup(int cnt)
{
    t[cnt].ans1=t[lc].ans1*t[rc].ans1;
    t[cnt].ans2=t[lc].ans2*t[rc].ans2;
}

void pushdown(int cnt)
{
    if(t[cnt].laz)
    {
        swap(t[lc].ans1,t[lc].ans2);
        swap(t[rc].ans1,t[rc].ans2);
        t[lc].laz^=1,t[rc].laz^=1;
        t[cnt].laz=0;
    }
}

void build(int l,int r,int cnt)
{
    t[cnt].l=l,t[cnt].r=r;
    t[cnt].laz=0;
    if(l==r)
    {
        if(str[l]=='A')
            t[cnt].ans1=a,t[cnt].ans2=b;
        else t[cnt].ans1=b,t[cnt].ans2=a;
        return ;
    }
    build(l,tmid,lc);
    build(tmid+1,r,rc);
    pushup(cnt);
}

void change(int l,int r,int cnt)
{
    if(l<=t[cnt].l&&t[cnt].r<=r)
    {
        swap(t[cnt].ans1,t[cnt].ans2);
        t[cnt].laz^=1;
        return ;
    }
    pushdown(cnt);
    if(l<=t[lc].r) change(l,r,lc);
    if(r>=t[rc].l) change(l,r,rc);
    pushup(cnt);
}


void ask(int l,int r,int cnt)
{
    if(l<=t[cnt].l&&t[cnt].r<=r)
    {
        ans=ans*t[cnt].ans1;
        return ;
    }
    pushdown(cnt);
    if(l<=t[lc].r) ask(l,r,lc);
    if(r>=t[rc].l) ask(l,r,rc);
}

int main(void)
{
    int n,q;
    scanf("%d%d",&n,&q);
    scanf("%s",str+1);
    build(1,n,1);
    int op,x,y,a,b;
    for(int i=1;i<=q;i++)
    {
        scanf("%d",&op);
        if(op==1)
        {
            scanf("%d%d",&x,&y);
            change(x,y,1);
        }
        else
        {
            scanf("%d%d%d%d",&x,&y,&a,&b);
            ans.init();
            ask(x,y,1);
            printf("%lld %lld\n",(a*ans.a[1][1]%mod+b*ans.a[2][1]%mod)%mod,(a*ans.a[1][2]%mod+b*ans.a[2][2]%mod)%mod);
        }
    }
    return 0;
}