1 条题解
-
0
搬运工 (syrth0p1) LV 10 @ 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