牛客挑战赛39 C牛牛的等差数列 线段树维护等差数列

#include <bits/stdc++.h>
#define LL long long
using namespace std;
#define mid (l+r>>1)

LL a[200000*4+10], sum[200000*4+10], a1[200000*4+10], d[200000*4+10];
const LL mod=26771144400;
LL slsum(LL a1, LL d, LL n){
    if(n%2==0){
        return (n*a1+((n/2)*(n-1))%mod*d)%mod;
    }
    else{
        return (n*a1+(((n-1)/2)*(n))%mod*d)%mod;
    }
}

void BT(LL i, LL l, LL r){
    sum[i]=a1[i]=d[i]=0;
    if(l==r){
        sum[i]=a[l];
        return ;
    }
    BT(i<<1, l, mid); BT(i<<1|1, mid+1, r);
    sum[i]=(sum[i<<1]+sum[i<<1|1])%mod;
}

void down(LL i, LL l, LL r){
    if(a1[i]||d[i]){
        a1[i<<1]=(a1[i<<1]+a1[i])%mod;
        d[i<<1]=(d[i<<1]+d[i])%mod;
        sum[i<<1]=(sum[i<<1]+slsum(a1[i], d[i], mid-l+1))%mod;


        a1[i<<1|1]=(a1[i<<1|1]+a1[i]+(mid-l+1)*d[i])%mod;
        d[i<<1|1]=(d[i<<1|1]+d[i])%mod;
        sum[i<<1|1]=(sum[i<<1|1]+slsum((a1[i]+(mid-l+1)*d[i]%mod)%mod, d[i], r-(mid+1)+1))%mod;

        a1[i]=d[i]=0;
        return ;
    }
}

void add(LL i, LL l, LL r, LL L, LL R, LL v, LL D){

    if(l==L&&r==R){
        a1[i]+=v; d[i]+=D;
        a1[i]%=mod; d[i]%=mod;
        sum[i]+=slsum(v, D, r-l+1);
        sum[i]%=mod;
        return ;
    }
    down(i, l, r);

    if(R<=mid) add(i<<1, l, mid, L, R, v, D);
    else if(L>mid) add(i<<1|1, mid+1, r, L, R, v, D);
    else add(i<<1, l, mid, L, mid, v, D), add(i<<1|1, mid+1, r, mid+1, R, (v+(mid+1-L)*D%mod)%mod, D);
    sum[i]=(sum[i<<1]+sum[i<<1|1])%mod;
}

LL ans=0, m;
void query(LL i, LL l, LL r, LL L, LL R){
    if(l==L&&r==R){
        ans+=sum[i];
        ans%=m;
        return ;
    }
    down(i, l, r);

    if(R<=mid) return query(i<<1, l, mid, L, R);
    if(L>mid) return query(i<<1|1, mid+1, r, L, R);
    return query(i<<1, l, mid, L, mid), query(i<<1|1, mid+1, r, mid+1, R);
}

inline LL read(){
    LL x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

int main(){

    int n, q; scanf("%d", &n);
    for(int i=1; i<=n; i++){
        a[i]=read();
    }
    BT(1, 1, n);
    scanf("%d", &q);
    while(q--){
        LL op, l, r, v, d;
        op=read();
        if(op==1){
            l=read(), r=read(), v=read(), d=read();
            add(1, 1, n, l, r, v, d);
        }
        else{
            ans=0;
            l=read(), r=read(), m=read();
            query(1, 1, n, l, r);
            printf("%lld\n", ans);
        }
    }

    return 0;
}