牛客oj小Cの棋王の道(暴力ブロック+ブロック再構築)

転送ドアのWAは12発も通っていない.主に区間賦値の操作が複雑になったと思う.出会った問題を分かち合う.問題を考慮して与えたいくつかの操作:1.区間プラス区間でこの2つに乗るのは難しくないので、乗るときにブロックの中の加算マークも乗せればいいです.2区間賦値これは、実は上の2つの操作で導き出すことができ、1つのマークを追加して記録しないでください(速度が遅く、コードの難易度が高くなります).0に乗ってxを加えればOKです.3 xを末尾に追加する.この操作は、最後のブロックのサイズを大きくする可能性がある.この操作がsqrt(n)を超えるときにブロックを再構成することができる.この回数は一度にO(n)である.しかもsqrt(n)回を超えることはない.複雑度の面ではブロックがsqrt(n)をとると全体的にO(nsqrt(n))である.テーマは3 sです.だからかろうじて足りる.型取り演算を減らすことに注意する.2つのintmaxを掛けるとlonglongmaxは爆発しません.だから真ん中に型を取らなくてもいいです.コード#コード#

#pragma GCC optimize(2)
#define LL long long
#define pq priority_queue
#define ULL unsigned long long
#define pb push_back
#define mem(a,x) memset(a,x,sizeof a)
#define pii pair
#define fir(i,a,b) for(int i=a;i<=b;++i)
#define afir(i,a,b) for(int i=a;i>=b;--i)
#define ft first
#define vi vector
#define sd second
#define ALL(a) a.begin(),a.end()
#include 
  
using namespace std;
const int N = 2e5+10;
  
inline LL read(){
    LL x = 0,f=1;char ch = getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,blo,num,mod,pos[N];
LL L[N],R[N],sum[N],add[N],mul[N],a[N];
void clr(int i){
    fir(j,L[i],R[i]) a[j] = (a[j]*mul[i]+ add[i])%mod;
    sum[i] = (sum[i]*mul[i]+(R[i]-L[i]+1)*add[i])%mod;
    add[i] = 0;mul[i] = 1;
}
bool f = 0;
void build(){
    if(f){
        fir(i,1,num){
            clr(i);
        }
    }
    blo = sqrt(n);
    num = n/blo;
    fir(i,1,num){
        L[i] = (i-1)*blo+1;
        R[i] = i*blo;
    }
    if(n % blo){
        num++;
        L[num] = R[num-1]+1;
        R[num] = n;
    }
    if(!f){
        f = 1;
        fir(i,1,N-1) add[i] = 0,sum[i] = 0,mul[i] = 1;
        fir(i,1,num){
            sum[i] = 0;add[i] = 0;mul[i] = 1;
            fir(j,L[i],R[i]){
                sum[i] = (sum[i] + a[j])%mod;
                pos[j] = i;
            }
        }
        return;
    }
    fir(i,1,num){
        sum[i] = 0;add[i] = 0;mul[i] = 1;
        fir(j,L[i],R[i]){
            sum[i] = (sum[i] + a[j])%mod;
            pos[j] = i;
        }
    }
}
void Add(int l,int r,LL v){
    int p = pos[l],q = pos[r];
    if(p == q){
        clr(p);
        fir(i,l,r) a[i] = (a[i] + v)%mod,sum[p] = (sum[p]+v)%mod;
    }
    else{
        fir(i,p+1,q-1){
            add[i] = (add[i] + v)%mod;
        }
        clr(p);
        fir(i,l,R[p]) a[i] = (a[i] + v)%mod;
        sum[p] = (sum[p] + (R[p]-l+1)*v)%mod;
        clr(q);
        fir(i,L[q],r) a[i] = (a[i] + v)%mod;
        sum[q] = (sum[q] + (r-L[q]+1)*v)%mod;
    }
}
void Mul(int l,int r,LL v){
    int p = pos[l],q = pos[r];
    if(p == q){
        clr(p);
        fir(i,l,r){
            sum[p] = (sum[p]-a[i]+mod)%mod;
            a[i] = a[i]*v%mod;
            sum[p] = (sum[p]+a[i])%mod;
        }
    }
    else{
        fir(i,p+1,q-1){
            mul[i] = (mul[i]*v)%mod,add[i] = add[i]*v%mod;
        }
        clr(p);
        fir(i,l,R[p]){
            sum[p] = (sum[p]-a[i]+mod)%mod;
            a[i] = a[i]*v%mod;
            sum[p] = (sum[p]+a[i])%mod;
        }
        clr(q);
        fir(i,L[q],r){
            sum[q] = (sum[q]-a[i]+mod)%mod;
            a[i] = a[i]*v%mod;
            sum[q] = (sum[q]+a[i])%mod;
        }
    }
}
LL query(int l,int r){
    int p = pos[l],q = pos[r];
    LL res = 0;
    if(p == q){
        clr(p);
        fir(i,l,r){
            res = (res + a[i])%mod;
        }
    }
    else{
        fir(i,p+1,q-1){;
            res = (res + sum[i]*mul[i] + (R[i]-L[i]+1)*add[i])%mod;
        }
        clr(p);
        fir(i,l,R[p]){
            res = (res + a[i])%mod;
        }
        clr(q);
        fir(i,L[q],r){
            res = (res + a[i])%mod;
        }
    }
    return res;
}
int main(){
    n = read(); m = read(); mod = read();
    fir(i,1,n) a[i] = read();
    build();
    int cnt = 0;
    while(m--){
        int op,l,r,x;
        cin >> op;
        if(op <= 3){
            l = read(); r =read(); x= read();
            if(op == 1) Add(l,r,x);
            else if(op == 2) Mul(l,r,x);
            else{
            	Mul(l,r,0);
            	Add(l,r,x);
            }
        }
        else if(op == 4){
            cnt++;
            x = read();
            a[++n] = x;
            clr(num);
            R[num]++;
            sum[num] = (sum[num]+x)%mod;
            pos[n] = num;
            if(cnt > blo){
                build();
                cnt = 0;
            }
        }
        else{
            l = read(); r = read();
            printf("%lld
",query(l,r));
        }
    }
      
    return 0;
}