线段树样例RE求调
查看原帖
线段树样例RE求调
809765
Limitless_lmw楼主2024/5/14 17:35

RT

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define MAXN 100005

struct Segment_Tree
{
    // ll l,r;
    ll summ;
    // #define ls(i) tree[i].l
    // #define rs(i) tree[i].r
    #define ls(i) (i<<1)
    #define rs(i) (i<<1|1)
    #define sum(i) tree[i].summ
}tree[MAXN<<2];

ll tag[MAXN<<2],a[MAXN];
ll n,m;

void build(ll p,ll l,ll r){
    tag[p]=0;
    // ls(p)=l,rs(p)=r;
    if(l==r){
        sum(p)=a[l];
        return ;
    }
    build(ls(p),l,(l+r)>>1);
    build(rs(p),((l+r)>>1)+1,r);
    sum(p)=sum(ls(p))+sum(rs(p));
    return ;
}

inline void f(ll p,ll l,ll r,ll k)
{
    tag[p]=tag[p]+k;
    sum(p)=sum(p)+k*(r-l+1);
    return;
}

inline void spread(ll p,ll l,ll r){
    ll mid=(l+r)>>1;
    f(ls(p),l,mid,tag[p]);
    f(rs(p),mid+1,r,tag[p]);
    tag[p]=0;
    return ;
}

inline void update(ll sx,ll sy,ll l,ll r,ll p,ll k){
    if(l>=sx&&r<=sy){
        tag[p]+=k;
        sum(p)+=((r-l+1)*k);
        return ;
    }
    spread(p,l,r);
    ll mid = (l+r)>>1;
    if(sx<=mid) update(sx,sy,l,mid,ls(p),k);
    if(sy>mid) update(sx,sy,mid+1,r,rs(p),k);
    sum(p)=sum(ls(p))+sum(rs(p));
    return ;
}

inline ll query(ll sx,ll sy,ll l,ll r,ll p){
    if(sx<=l&&sy>=r) return sum(p);
    ll res=0;
    ll mid=(l+r)>>1;
    spread(p,l,r);
    if(sx<=mid) res+=query(sx,sy,l,mid,ls(p));
    if(sy>mid) res+=query(sx,sy,mid+1,r,rs(p));
    return res;
}

int main()
{
    int n,m,opt,l,r,k,d,t;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=n-1;i>0;i--)
        a[i+1]=a[i+1]-a[i];
    build(1,1,n);
    for(int i=0;i<m;i++){
        cin>>opt;
        if(opt==1){
            cin>>l>>r>>k>>d;
            update(1,1,n,l,l,k);
            if(l+1<=r) update(1,1,n,l+1,r,d);
            if(r<n) update(1,1,n,r+1,r+1,-(k+d*(r-l)));
        }
        else{
            cin>>t;
            cout<<query(1,1,n,1,t)<<'\n';
        }
        
    }
    return 0;
}
2024/5/14 17:35
加载中...