91pts求助
查看原帖
91pts求助
719611
__2304__楼主2024/10/12 19:13
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+5;
struct SegmentTree{
    ll l,r,sum,add;
    #define l(x) t[x].l
    #define r(x) t[x].r
    #define sum(x) t[x].sum
    #define add(x) t[x].add
}t[N*4];
ll n,m,a[N],d[N];
void build(ll p,ll l,ll r){
    l(p)=l,r(p)=r;
    if(l==r){
        sum(p)=d[l];
        return;
    }
    ll mid=(l+r)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    sum(p)=sum(p*2)+sum(p*2+1);
}
void spread(ll p){
    if(add(p)){
        sum(p*2)+=add(p)*(r(p*2)-l(p*2)+1);
        sum(p*2+1)+=add(p)*(r(p*2+1)-l(p*2+1)+1);
        add(p*2)+=add(p);
        add(p*2+1)+=add(p);
        add(p)=0;
    }
}
void change(ll p,ll l,ll r,ll d){
    if(l<=l(p)&&r>=r(p)){
        sum(p)+=d*(r(p)-l(p)+1);
        add(p)+=d;
        return;
    }
    spread(p);
    ll mid=(l(p)+r(p))/2;
    if(l<=mid) change(p*2,l,r,d);
    if(r>mid) change(p*2+1,l,r,d);
    sum(p)=sum(p*2)+sum(p*2+1);
}
ll ask(ll p,ll l,ll r){
    if(l<=l(p)&&r>=r(p)) return sum(p);
    spread(p);
    ll mid=(l(p)+r(p))/2,val=0;
    if(l<=mid) val+=ask(p*2,l,r);
    if(r>mid) val+=ask(p*2+1,l,r);
    return val;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) d[i]=a[i]-a[i-1];
    build(1,1,n);
    for(int i=1;i<=m;i++){
        int opt;
        cin>>opt;
        if(opt==1){
            ll l,r,K,D;
            cin>>l>>r>>K>>D;
            change(1,l,l,K);
            if(r+1<=n) change(1,r+1,r+1,-(K+D*(r-l)));
            change(1,l+1,r,D);
        }
        else if(opt==2){
            ll p;
            cin>>p;
            cout<<ask(1,1,p)<<endl;
        }
    }
    return 0;
}
2024/10/12 19:13
加载中...