废了……求助！给解决方案

常规
44

效果一样

45 
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int MAX_N=1e6+10;
const int MX=100;
const ll BASE=131;
const ll MOD=10000000007;
const int mxN=84;
const int mxK=14;
const int MAXSIZE=300;
ll n,m,z[MAX_N];
typedef struct ST{
    ll ans[MAX_N]={0},sum[MAX_N],add[MAX_N]={0},p;
    inline ll lch(ll a){return (a<<1);}
    inline ll rsh(ll a){return (a<<1|1);}
    inline void pushdown(ll a,ll l,ll r){
        ll mid=(l+r)>>1;
        ll ls=lch(a),rs=rsh(a);
        ans[ls]=(ans[ls]*sum[a]%p+add[a]*(mid-l+1)%p)%p;
        ans[rs]=(ans[rs]*sum[a]%p+add[a]*(r-mid)%p)%p;
        sum[ls]=(sum[ls]*sum[a])%p;
        sum[rs]=(sum[rs]*sum[a])%p;
        add[ls]=(add[ls]*sum[a]%p+add[a])%p;
        add[rs]=(add[rs]*sum[a]%p+add[a])%p;
        sum[a]=1;
        add[a]=0;
        return;
    }
    inline void biuding(ll a,ll l,ll r,ll *v){
        for(int i=0;i<=(n<<2);i++)sum[i]=1;
        if(l==r){ans[a]=v[l]%p;}
        else{
            ll mid=(l+r)>>1;
            biuding(lch(a),l,mid,v);
            biuding(rsh(a),mid+1,r,v);
            ans[a]=(ans[lch(a)]+ans[rsh(a)])%p;
        }
        return;
    }
    inline void toUP(ll tl,ll tr,ll l,ll r,ll a,ll b,bool type){
        if(tl<=l&&r<=tr){
            if(type){
                ans[a]=b*ans[a]%p;
                sum[a]=sum[a]*b%p;
                add[a]=add[a]*b%p;
            }else{
                ans[a]=(ans[a]+b*(r-l+1))%p;
                add[a]=(add[a]+b)%p;
            }
            return;
        }
        pushdown(a,l,r);
        ll mid=(l+r)>>1;
        if(tl<=mid)toUP(tl,tr,l,mid,lch(a),b,type);
        if(tr>mid)toUP(tl,tr,mid+1,r,rsh(a),b,type);
        ans[a]=(ans[lch(a)]+ans[rsh(a)])%p;
        return;
    }
    inline ll range(ll tl,ll tr,ll l,ll r,ll a){
        ll cnt=0;
        if(tl<=l&&r<=tr)return ans[a]%p;
        ll mid=(l+r)>>1;
        pushdown(a,l,r);
        if(tl<=mid)cnt+=range(tl,tr,l,mid,lch(a))%p;
        if(tr>mid)cnt+=range(tl,tr,mid+1,r,rsh(a))%p;
        return cnt%p;
    } 
}ST;
ST st;
int main(){
    cin>>n>>m>>st.p;
    ll a,l,r,k;
    for(ll i=1;i<=n;i++)cin>>z[i];
    st.biuding(1,1,n,z);
    for(ll i=0;i<m;i++){
        cin>>a>>l>>r;
        if(a==1){
            cin>>k;
            st.toUP(1,n,l,r,1,k%st.p,true);
        }else if(a==2){
            cin>>k;
            st.toUP(1,n,l,r,1,k%st.p,false);
        }else{
            printf("%lld\n",st.range(l,r,1,n,1)%st.p);
        }
    }
    return 0;
}

输出:

18
14
46

哎不对啊还是toUP参数的锅，tl和tr是目标，参数应该是l,r,1,n,1,k%st.p,false/true

47

??
image

48

样例是对了，TLE30

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int MAX_N=1e6+10;
const int MX=100;
const ll BASE=131;
const ll MOD=10000000007;
const int mxN=84;
const int mxK=14;
const int MAXSIZE=300;
ll n,m,z[MAX_N];
typedef struct ST{
    ll ans[MAX_N]={0},sum[MAX_N],add[MAX_N]={0},p;
    inline ll lch(ll a){return (a<<1);}
    inline ll rsh(ll a){return (a<<1|1);}
    inline void pushdown(ll a,ll l,ll r){
        ll mid=(l+r)>>1;
        ll ls=lch(a),rs=rsh(a);
        ans[ls]=(ans[ls]*sum[a]%p+add[a]*(mid-l+1)%p)%p;
        ans[rs]=(ans[rs]*sum[a]%p+add[a]*(r-mid)%p)%p;
        sum[ls]=(sum[ls]*sum[a])%p;
        sum[rs]=(sum[rs]*sum[a])%p;
        add[ls]=(add[ls]*sum[a]%p+add[a])%p;
        add[rs]=(add[rs]*sum[a]%p+add[a])%p;
        sum[a]=1;
        add[a]=0;
        return;
    }
    inline void biuding(ll a,ll l,ll r,ll *v){
        for(int i=0;i<=(n<<2);i++)sum[i]=1;
        if(l==r){ans[a]=v[l]%p;}
        else{
            ll mid=(l+r)>>1;
            biuding(lch(a),l,mid,v);
            biuding(rsh(a),mid+1,r,v);
            ans[a]=(ans[lch(a)]+ans[rsh(a)])%p;
        }
        return;
    }
    inline void toUP(ll tl,ll tr,ll l,ll r,ll a,ll b,bool type){
        if(tl<=l&&r<=tr){
            if(type){
                ans[a]=b*ans[a]%p;
                sum[a]=sum[a]*b%p;
                add[a]=add[a]*b%p;
            }else{
                ans[a]=(ans[a]+b*(r-l+1))%p;
                add[a]=(add[a]+b)%p;
            }
            return;
        }
        pushdown(a,l,r);
        ll mid=(l+r)>>1;
        if(tl<=mid)toUP(tl,tr,l,mid,lch(a),b,type);
        if(tr>mid)toUP(tl,tr,mid+1,r,rsh(a),b,type);
        ans[a]=(ans[lch(a)]+ans[rsh(a)])%p;
        return;
    }
    inline ll range(ll tl,ll tr,ll l,ll r,ll a){
        ll cnt=0;
        if(tl<=l&&r<=tr)return ans[a]%p;
        ll mid=(l+r)>>1;
        pushdown(a,l,r);
        if(tl<=mid)cnt+=range(tl,tr,l,mid,lch(a))%p;
        if(tr>mid)cnt+=range(tl,tr,mid+1,r,rsh(a))%p;
        return cnt%p;
    } 
}ST;
ST st;
int main(){
    cin>>n>>m>>st.p;
    ll a,l,r,k;
    for(ll i=1;i<=n;i++){
        cin>>z[i];
        z[i]%=st.p;
    }
    st.biuding(1,1,n,z);
    for(ll i=0;i<m;i++){
        cin>>a>>l>>r;
        if(a==1){
            cin>>k;
            st.toUP(l,r,1,n,1,k%st.p,true);
        }else if(a==2){
            cin>>k;
            st.toUP(l,r,1,n,1,k%st.p,false);
        }else{
            printf("%lld\n",st.range(l,r,1,n,1)%st.p);
        }
    }
    return 0;
}
49

坏了，TLE就难了

50

build运行一次把对应位置设置为1就行了，把初始化改为sum[a]=1

1 个赞
51

A了

52

有实力的

53

666