超简单题解

#include<iostream>
#include<algorithm>
#include<cstdio>
#define LSON rt<<1
#define RSON rt<<1|1
#define DATA(x,i,j) a[x].data[i-1][j-1]
#define SUM(x,i,j) a[x].sum[i-1][j-1]//为了省空间只能这么干了。。。
#define ADD(x) a[x].c
#define DEL(x) a[x].d
#define LSIDE(x) a[x].l
#define RSIDE(x) a[x].r
#define WIDTH(x) (RSIDE(x)-LSIDE(x)+1)
#define MAXN 300010
#define MOD 1000000007LL
using namespace std;
int n,m;
long long A,B,inv,f[MAXN][4];
struct node{
    long long val[4][4];
    inline void clean(){
        for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
        val[i][j]=(i==j);
    }
    friend node operator *(const node x,const node y){
        node ret;
        for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++){
            ret.val[i][j]=0;
            for(int k=1;k<=3;k++)ret.val[i][j]=(ret.val[i][j]+x.val[i][k]*y.val[k][j]%MOD)%MOD;
        }
        ret.val[3][3]=1;
        return ret;
    }
}one,two,power[35];
struct Segment_Tree{
    long long sum[3][3],data[3][3];
    int c,d,l,r;
}a[MAXN<<2];
inline long long read(){
    long long date=0,w=1;char c=0;
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
    return date*w;
}
long long mexp(long long a,long long b,long long c){
    long long s=1;
    while(b){
        if(b&1)s=s*a%c;
        a=a*a%c;
        b>>=1;
    }
    return s;
}
node pow(long long k){
    node s;
    s.clean();
    int i=1;
    while(k){
        if(k&1)s=s*power[i];
        k>>=1;
        i++;
    }
    return s;
}
void function(int i){
    node s=one*pow(f[i][0]-2);
    f[i][1]=s.val[1][2];f[i][2]=s.val[1][1];
}
void build(){
    one.val[1][1]=2;one.val[1][2]=one.val[1][3]=1;
    two.val[1][1]=two.val[1][2]=two.val[3][3]=1;
    two.val[2][1]=A;two.val[3][1]=B;
    for(int i=1;i<=32;i++){
        power[i]=two;
        two=two*two;
    }
}
inline void pushup(int rt){
    for(int i=1;i<=3;i++)
    for(int j=1;j<=3;j++){
        DATA(rt,i,j)=(DATA(LSON,i,j)+DATA(RSON,i,j))%MOD;
        SUM(rt,i,j)=(SUM(LSON,i,j)+SUM(RSON,i,j))%MOD;
    }
}
inline void add(int rt,int l){
    for(int i=1;i<=2;i++)SUM(rt,l,i)=SUM(rt,l,i+1);
    SUM(rt,l,3)=(SUM(rt,l,2)+A*SUM(rt,l,1)%MOD+B*WIDTH(rt)%MOD)%MOD;
    if(l==1){
        for(int i=1;i<=2;i++)
        for(int j=1;j<=3;j++)
        DATA(rt,i,j)=DATA(rt,i+1,j);
        for(int i=1;i<=3;i++)DATA(rt,3,i)=(DATA(rt,2,i)+A*DATA(rt,1,i)%MOD+B*SUM(rt,2,i)%MOD)%MOD;
    }
    else{
        for(int i=1;i<=3;i++)
        for(int j=1;j<=2;j++)
        DATA(rt,i,j)=DATA(rt,i,j+1);
        for(int i=1;i<=3;i++)DATA(rt,i,3)=(DATA(rt,i,2)+A*DATA(rt,i,1)%MOD+B*SUM(rt,1,i)%MOD)%MOD;
    }
}
inline void del(int rt,int l){
    if(A==0){
        for(int i=2;i>=1;i--)SUM(rt,l,i+1)=SUM(rt,l,i);
        SUM(rt,l,1)=(SUM(rt,l,2)-B*WIDTH(rt)%MOD+MOD)%MOD;
        if(l==1){
            for(int i=2;i>=1;i--)
            for(int j=1;j<=3;j++)
            DATA(rt,i+1,j)=DATA(rt,i,j);
            for(int i=1;i<=3;i++)DATA(rt,1,i)=(DATA(rt,2,i)-B*SUM(rt,2,i)%MOD+MOD)%MOD;
        }
        else{
            for(int i=1;i<=3;i++)
            for(int j=2;j>=1;j--)
            DATA(rt,i,j+1)=DATA(rt,i,j);
            for(int i=1;i<=3;i++)DATA(rt,i,1)=(DATA(rt,i,2)-B*SUM(rt,1,i)%MOD+MOD)%MOD;
        }
        return;
    }
    for(int i=2;i>=1;i--)SUM(rt,l,i+1)=SUM(rt,l,i);
    SUM(rt,l,1)=((SUM(rt,l,3)-SUM(rt,l,2)-B*WIDTH(rt)%MOD)*inv%MOD+MOD)%MOD;
    if(l==1){
        for(int i=2;i>=1;i--)
        for(int j=1;j<=3;j++)
        DATA(rt,i+1,j)=DATA(rt,i,j);
        for(int i=1;i<=3;i++)DATA(rt,1,i)=((DATA(rt,3,i)-DATA(rt,2,i)-B*SUM(rt,2,i)%MOD)*inv%MOD+MOD)%MOD;
    }
    else{
        for(int i=1;i<=3;i++)
        for(int j=2;j>=1;j--)
        DATA(rt,i,j+1)=DATA(rt,i,j);
        for(int i=1;i<=3;i++)DATA(rt,i,1)=((DATA(rt,i,3)-DATA(rt,i,2)-B*SUM(rt,1,i)%MOD)*inv%MOD+MOD)%MOD;
    }
}
inline void pushdown_sign(int rt,int l,int c){
    if(!c)return;
    if(c>0)for(int i=1;i<=c;i++)add(rt,l);
    else for(int i=-1;i>=c;i--)del(rt,l);
}
inline void pushdown(int rt){
    if(LSIDE(rt)==RSIDE(rt))return;
    ADD(LSON)+=ADD(rt);DEL(LSON)+=DEL(rt);
    pushdown_sign(LSON,1,ADD(rt));pushdown_sign(LSON,2,DEL(rt));
    ADD(RSON)+=ADD(rt);DEL(RSON)+=DEL(rt);
    pushdown_sign(RSON,1,ADD(rt));pushdown_sign(RSON,2,DEL(rt));
    ADD(rt)=DEL(rt)=0;
}
void buildtree(int l,int r,int rt){
    LSIDE(rt)=l;RSIDE(rt)=r;ADD(rt)=DEL(rt)=0;
    if(l==r){
        for(int i=1;i<=3;i++){
            SUM(rt,1,i)=f[l-1][i];
            SUM(rt,2,i)=f[l+1][i];
        }
        for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
        DATA(rt,i,j)=SUM(rt,1,i)*SUM(rt,2,j)%MOD;
        return;
    }
    int mid=LSIDE(rt)+RSIDE(rt)>>1;
    buildtree(l,mid,LSON);
    buildtree(mid+1,r,RSON);
    pushup(rt);
}
void update_add(int l,int r,int c,int rt){
    if(l<=LSIDE(rt)&&RSIDE(rt)<=r){
        ADD(rt)+=c;
        pushdown_sign(rt,1,c);
        return;
    }
    pushdown(rt);
    int mid=LSIDE(rt)+RSIDE(rt)>>1;
    if(l<=mid)update_add(l,r,c,LSON);
    if(mid<r)update_add(l,r,c,RSON);
    pushup(rt);
}
void update_del(int l,int r,int c,int rt){
    if(l<=LSIDE(rt)&&RSIDE(rt)<=r){
        DEL(rt)+=c;
        pushdown_sign(rt,2,c);
        return;
    }
    pushdown(rt);
    int mid=LSIDE(rt)+RSIDE(rt)>>1;
    if(l<=mid)update_del(l,r,c,LSON);
    if(mid<r)update_del(l,r,c,RSON);
    pushup(rt);
}
long long query(int l,int r,int rt){
    if(l>r)return 0;
    long long ans=0;
    if(l<=LSIDE(rt)&&RSIDE(rt)<=r)return DATA(rt,3,1);
    pushdown(rt);
    int mid=LSIDE(rt)+RSIDE(rt)>>1;
    if(l<=mid)ans=(ans+query(l,r,LSON))%MOD;
    if(mid<r)ans=(ans+query(l,r,RSON))%MOD;
    return ans;
}
void work(){
    char ch[7];
    int x,y,l,r;
    while(m--){
        scanf("%s",ch);x=read();y=read();
        if(ch[0]=='p'){
            l=x+1;r=y+1;
            if(r>n)r=n;
            if(l<=r)update_add(l,r,1,1);
            l=x-1;r=y-1;
            if(l<1)l=1;
            if(l<=r)update_del(l,r,1,1);
        }
        else if(ch[0]=='m'){
            l=x+1;r=y+1;
            if(r>n)r=n;
            if(l<=r)update_add(l,r,-1,1);
            l=x-1;r=y-1;
            if(l<1)l=1;
            if(l<=r)update_del(l,r,-1,1);
        }
        else printf("%lld\n",query(x+1,y-1,1));
    }
}
void init(){
    n=read();m=read();A=read();B=read();
    inv=mexp(A,MOD-2,MOD);
    build();
    for(int i=1;i<=n;i++){
        f[i][0]=read();
        function(i);
        f[i][3]=(f[i][2]+f[i][1]*A%MOD+B)%MOD;
    }
    buildtree(1,n,1);
}
int main(){
    init();
    work();
    return 0;
}

真的非常简单