#10129. 「一本通 4.3 练习 3」维护序列

2019-01-28 14:29:59


10129. 「一本通 4.3 练习 3」维护序列

题意

有长为 $n$ 的数列,不妨设为 $a_1,a_2,\cdots ,a_n$ 。有如下三种操作形式:

  • 把数列中的一段数全部乘一个值;
  • 把数列中的一段数全部加一个值;
  • 询问数列中的一段数的和,由于答案可能很大,你只需输出这个数模 $P$ 的值。

思路

线段树瞎搞。乘法的优先级要高一些。

注意MOD

#include<bits/stdc++.h>
#define N 10000000+10
#define ll long long
using namespace std;
ll n,m,a[N],add[N*4+10],mod,p,mul[N*4+10];
ll tree[N*4+10];
void pushup(ll id){
    tree[id]=tree[id<<1]+tree[(id<<1)|1];
    tree[id]%=mod;
}
void push_down(ll cur,ll l,ll r,ll mid){
    if(mul[cur]==1&&add[cur]==0) return;
    mul[cur<<1]=mul[cur<<1]*mul[cur]%mod;
    add[cur<<1]=(add[cur<<1]*mul[cur]%mod+add[cur])%mod;
    tree[cur<<1]=(tree[cur<<1]*mul[cur]%mod+add[cur]*(ll)(mid-l+1)%mod)%mod;
    mul[cur<<1|1]=mul[cur<<1|1]*mul[cur]%mod;
    add[cur<<1|1]=(add[cur<<1|1]*mul[cur]%mod+add[cur])%mod;
    tree[cur<<1|1]=(tree[cur<<1|1]*mul[cur]%mod+add[cur]*(ll)(r-mid)%mod)%mod;
    mul[cur]=1;
    add[cur]=0;
    return;
}
void update(ll id,ll l,ll r,ll ql,ll qr,ll val){
    if(ql<=l&&qr>=r){
        add[id]+=val;add[id]%=mod;
        tree[id]=(tree[id]+(ll)(r-l+1)*val%mod)%mod;
        return ;
    }
    push_down(id,l,r,l+r>>1);
    ll mid=l+((r-l)>>1);
    if(ql<=mid) update(id<<1,l,mid,ql,qr,val);
    if(qr>=mid+1) update((id<<1)|1,mid+1,r,ql,qr,val);
    pushup(id);
}
void updatemul(ll cur,ll L,ll R,ll l,ll r,ll x){
    if(L>=l&&R<=r){
        mul[cur]=mul[cur]*(ll)x%mod;
        add[cur]=add[cur]*(ll)x%mod;
        tree[cur]=tree[cur]*(ll)x%mod;
        return;
    }
    ll mid=L+R>>1;
    push_down(cur,L,R,mid);
    if(l<=mid) updatemul(cur<<1,L,mid,l,r,x);
    if(r>mid) updatemul(cur<<1|1,mid+1,R,l,r,x);
    pushup(cur);
}
ll query(ll id,ll L,ll R,ll l,ll r){
    if(L>=l&&R<=r) return tree[id]%mod;
    ll mid=L+R>>1;
    ll ans=0;
    push_down(id,L,R,mid);
    if(l<=mid) ans=(ans+query(id<<1,L,mid,l,r))%mod;
    if(r>mid) ans=(ans+query(id<<1|1,mid+1,R,l,r))%mod;
    pushup(id);
    return ans;
}
void build(ll L,ll R,ll x,ll y,ll cur){
    mul[cur]=1;add[cur]=0;tree[cur]+=y;
    if(L==R) return;
    ll mid=L+R>>1;
    if(x>mid) build(mid+1,R,x,y,cur<<1|1);
    else build(L,mid,x,y,cur<<1);
    pushup(cur);
}
int main(){
    scanf("%lld%lld",&n,&mod);
    for(ll i=1;i<=n;i++) scanf("%lld",&a[i]),build(1,n,i,a[i]%mod,1);
    scanf("%lld",&m);
    for(ll i=1;i<=m;i++){
        ll type;
        scanf("%lld",&type);
        if(type==1){
            ll x,y,k;
            scanf("%lld%lld%lld",&x,&y,&k);
            updatemul(1,1,n,x,y,k);
        }
        if(type==2){
            ll x,y,k;
            scanf("%lld%lld%lld",&x,&y,&k);
            update(1,1,n,x,y,k);
        }
        if(type==3){
            ll x,y;
            scanf("%lld%lld",&x,&y);
            ll temp=query(1,1,n,x,y);
            printf("%lld\n",temp%mod);
        }
    }
    return 0;
}