题解

1 条题解

  • 0
    @ 2025-06-09 20:21:08
    #include <bits/stdc++.h>
    #define lint long long
    using namespace std;
    inline int read(){
        char c;int f=1,res=0;
        while(c=getchar(),!isdigit(c))if(c=='-')f*=-1;
        while(isdigit(c))res=res*10+c-'0',c=getchar();
        return res*f;
    }
    const int N=3e5+5;
    const lint md=1e9+7;
    #define add(x,y) x=(x+y)%md
    struct mat{
        lint v[3][3];
        mat(lint x=0){
            memset(v,0,sizeof v);
            for(int i=0;i<3;++i)v[i][i]=x;
        }inline lint* operator[](int x)
            {return v[x];}
        inline mat operator*(mat x){
            mat r;
            for(int i=0;i<3;++i)
                for(int k=0;k<3;++k)
                    for(int j=0;j<3;++j)
                        add(r[i][j],v[i][k]*x[k][j]);
            return r;
        }inline mat operator+(mat x){
            for(int i=0;i<3;++i)
                for(int j=0;j<3;++j)
                    add(x[i][j],v[i][j]);
            return x;
        }inline mat T(){
            mat r;
            for(int i=0;i<3;++i)
                for(int j=0;j<3;++j)
                    r[i][j]=v[j][i];
            return r;
        }inline mat qpow(lint x){
            mat r(1),t=*this;
            while(x){
                if(x&1)r=r*t;
                t=t*t;x>>=1;
            }return r;
        }
    }pl,mi,tpl,tmi,f,tf;
    int n,nq;lint a,b,v[N];
    inline lint qpow(lint x,lint y=md-2){
        lint res=1;
        while(y){
            if(y&1)res=res*x%md;
            x=x*x%md;y>>=1;
        }return res;
    }
    inline void init(){
        pl[0][0]=pl[1][0]=pl[2][2]=1;
        pl[0][1]=a;pl[0][2]=b;
        f[0][0]=2;f[1][0]=f[2][0]=1;
        tpl=pl.T();tf=f.T();
        if(a){
            mi[0][1]=mi[2][2]=1;
            mi[1][0]=qpow(a);
            mi[1][1]=md-qpow(a);
            mi[1][2]=md-b*qpow(a)%md;
        }else{
            mi[0][1]=mi[1][1]=mi[2][2]=1;
            mi[1][2]=md-b;
        }tmi=mi.T();
    }
    mat s[N<<1],tl[N<<1],tr[N<<1];
    int ch[N<<1][2],tot,rt;
    inline void nupd(int x,mat lu,mat ru){
        tl[x]=lu*tl[x];tr[x]=tr[x]*ru;
        s[x]=lu*s[x]*ru;
    }inline void pushdown(int x){
        nupd(ch[x][0],tl[x],tr[x]);
        nupd(ch[x][1],tl[x],tr[x]);
        tl[x]=tr[x]=mat(1);
    }void build(int &x=rt,int l=2,int r=n-1){
        x=++tot;tl[x]=tr[x]=mat(1);
        if(l==r){
            s[x]=pl.qpow(v[l-1]-1)*f;
            s[x]=s[x]*tf*tpl.qpow(v[l+1]-3);
            return;
        }int mid=l+r>>1;
        build(ch[x][0],l,mid);
        build(ch[x][1],mid+1,r);
        s[x]=s[ch[x][0]]+s[ch[x][1]];
    }
    void upd(int lp,int rp,mat lu,mat ru,int x=rt,int l=2,int r=n-1){
        if(l>rp||r<lp)return;
        if(lp<=l&&r<=rp)return nupd(x,lu,ru);
        int mid=l+r>>1;pushdown(x);
        upd(lp,rp,lu,ru,ch[x][0],l,mid);
        upd(lp,rp,lu,ru,ch[x][1],mid+1,r);
        s[x]=s[ch[x][0]]+s[ch[x][1]];
    }
    mat query(int lp,int rp,int x=rt,int l=2,int r=n-1){
        if(l>rp||r<lp)return mat();
        if(lp<=l&&r<=rp)return s[x];
        int mid=l+r>>1;pushdown(x);
        mat res=query(lp,rp,ch[x][0],l,mid);
        res=res+query(lp,rp,ch[x][1],mid+1,r);
        return res;
    }
    int main(){
        n=read();nq=read();
        a=read();b=read();
        for(int i=1;i<=n;++i)v[i]=read();
        init();build();
        while(nq--){
            string op;cin>>op;
            int l=read(),r=read();
            if(op=="plus"){
                upd(l+1,r+1,pl,mat(1));
                upd(l-1,r-1,mat(1),tpl);
            }else if(op=="minus"){
                upd(l+1,r+1,mi,mat(1));
                upd(l-1,r-1,mat(1),tmi);
            }else if(op=="query")
                printf("%lld\n",query(l+1,r-1)[0][0]);
        }return 0;
    }
    
  • 1

信息

ID
1958
难度
7
分类
数据结构 | 线段树 点击显示
标签
递交数
109
已通过
22
通过率
20%
被复制
2
上传者