hdu6155

201708 （ACM）数据结构----线段树 （ACM）动态规划

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define mp make_pair
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define de(a) cout<<#a<<"="<<a<<endl;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
//--------
const int N=100005;
const ll mod=1e9+7;
int n,q;
int tag[N<<2];
char s[N];
ll a[N<<2],b[N<<2],c[N<<2],d[N<<2],e[N<<2],f[N<<2];
void up(int rt) {
    int l=(rt<<1);
    int r=(rt<<1|1);
    a[rt]=(a[r]*a[l]%mod+b[r]*d[l]%mod)%mod;
    b[rt]=(a[r]*b[l]%mod+b[r]*e[l]%mod)%mod;
    c[rt]=(a[r]*c[l]%mod+b[r]*f[l]%mod+c[r])%mod;
    d[rt]=(d[r]*a[l]%mod+e[r]*d[l]%mod)%mod;
    e[rt]=(d[r]*b[l]%mod+e[r]*e[l]%mod)%mod;
    f[rt]=(d[r]*c[l]%mod+e[r]*f[l]%mod+f[r])%mod;
}
void gao(int x) {
    swap(a[x],b[x]);
    swap(d[x],e[x]);
    swap(a[x],d[x]);
    swap(b[x],e[x]);
    swap(c[x],f[x]);
}
void down(int rt) {
    if(!tag[rt]) return ;
    gao(rt<<1);
    gao(rt<<1|1);
    tag[rt<<1]^=1;
    tag[rt<<1|1]^=1;
    tag[rt]=0;
}
void build(int l,int r,int rt) {
    if(l==r) {
        if(s[l-1]=='0') {
            a[rt]=b[rt]=c[rt]=e[rt]=1;
        } else {
            a[rt]=d[rt]=e[rt]=f[rt]=1;
        }
        return ;
    }
    int m=(l+r)>>1;
    build(lson);build(rson);
    up(rt);
}
void upd(int L,int R,int l,int r,int rt) {
    if(R<l||r<L) return ;
    if(L<=l&&r<=R) {
        tag[rt]^=1;
        gao(rt);
        return ;
    }
    int m=(l+r)>>1;
    down(rt);
    upd(L,R,lson);
    upd(L,R,rson);
    up(rt);
}
pair<ll,ll> calc(int t,ll x,ll y) {
    ll o=a[t]*x%mod+b[t]*y%mod+c[t];
    ll _=d[t]*x%mod+e[t]*y%mod+f[t];
    return mp(o%mod,_%mod);
}
pair<ll,ll> qry(int L,int R,ll x,ll y,int l,int r,int rt) {
    if(L<=l&&r<=R) return calc(rt,x,y);
    int m=(l+r)>>1;
    down(rt);
    if(m>=L) {
        pair<ll,ll> t=qry(L,R,x,y,lson);
        x=t.fi;y=t.se;
    }
    if(m+1<=R) { 
        pair<ll,ll> t=qry(L,R,x,y,rson);
        x=t.fi;y=t.se;
    }
    return mp(x,y);
}
int main() {
    int T;scanf("%d",&T);
    while(T--) {
        ///
        scanf("%d%d%s",&n,&q,s);
        ///init
        memset(tag,0,sizeof(tag));
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        memset(c,0,sizeof(c));
        memset(d,0,sizeof(d));
        memset(e,0,sizeof(e));
        memset(f,0,sizeof(f));
        ///solve
        build(1,n,1);
        while(q--) {
            int x,y,z;scanf("%d%d%d",&x,&y,&z);
            if(x==1) {
                upd(y,z,1,n,1);
            } else {
                pair<ll,ll> t=qry(y,z,0,0,1,n,1);
                ll ans=(t.fi+t.se)%mod;
                printf("%lld\n",ans);
            }
        }
    }
    return 0;
}