题解：P13979 数列分块入门 4

Cipher0128 · 2025-09-06 19:59:33 · 题解

可以用线段树。

本题中用线段树节点维护区间的和，节点有懒标记，下传时将左右儿子的区间和加上懒标记的值乘以对应区间长度即可。

注意和可能是负的，而答案需要是正的，所以取模后要加上模数再取模。

#include<bits/stdc++.h>
#define rd read()
#define ll long long
#define for_(a,b,c) for(int a=b;a<=c;++a)
#define lc (p<<1)
#define rc (p<<1|1)
#define md (l+r>>1)
using namespace std;
int n,m;
const int N=3e5+10;
ll a[N];
ll t[N<<2],lz[N<<2];
void pup(int p){
    t[p]=t[lc]+t[rc];
}
void pdn(int p,int l,int r){
    if(!lz[p])return;ll v=lz[p];lz[p]=0;
    t[lc]+=(md-l+1)*v,t[rc]+=(r-md)*v;
    lz[lc]+=v,lz[rc]+=v;
}
void build(int p,int l,int r){
    if(l==r)return t[p]=a[l],void();
    build(lc,l,md);build(rc,md+1,r);
    pup(p);
}
void mdf(int p,int l,int r,int x,int y,ll val){
    if(x<=l&&r<=y)return t[p]+=val*(r-l+1),lz[p]+=val,void();
    pdn(p,l,r);
    if(x<=md)mdf(lc,l,md,x,y,val);
    if(y>=md+1)mdf(rc,md+1,r,x,y,val);
    pup(p);
}
ll qry(int p,int l,int r,int x,int y){
    if(x<=l&&r<=y)return t[p];
    ll res=0;pdn(p,l,r);
    if(x<=md)res+=qry(lc,l,md,x,y);
    if(y>=md+1)res+=qry(rc,md+1,r,x,y);
    return res;
}
inline ll read(){ll d=0,f=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}while(ch<='9'&&ch>='0'){d=(d<<1)+(d<<3)+ch-'0';ch=getchar();}return f?-d:d;}
int main(){
    n=rd;
    for_(i,1,n)a[i]=rd;
    build(1,1,n);
    for_(I,1,n){
        ll op=rd,l=rd,r=rd,v=rd;
        if(op)printf("%lld\n",(qry(1,1,n,l,r)%(v+1)+v+1)%(v+1));
        else mdf(1,1,n,l,r,v);
    }
    return 0;
}