9pts 求调,开了 long long,而且没有越界
查看原帖
9pts 求调,开了 long long,而且没有越界
641953
Determination_Y楼主2023/8/6 12:50
#include <bits/stdc++.h>
#define int long long
using namespace std;

int type,l,r,K,D,p;
int n,m,a[100005];
int sum[100005];

struct Segment_Tree{
    struct Node{
        int value,lazytag;
        int l,r;
    }Tree[400005];

    void Push_up(int pos){
        Tree[pos].value=Tree[pos<<1].value+Tree[pos<<1|1].value;
    }

    void Push_down(int pos){
        auto &rt=Tree[pos];
        auto &l =Tree[pos<<1];
        auto &r =Tree[pos<<1|1];
        if(rt.lazytag){
            l.value+=rt.lazytag*(l.r-l.l+1);
            r.value+=rt.lazytag*(r.r-r.l+1);
            l.lazytag+=rt.lazytag;
            r.lazytag+=rt.lazytag;
            rt.lazytag=0;
        }
    }

    //建树
    void Build(int pos,int l,int r){
        Tree[pos]={0,0,l,r};
        if(l==r){
            Tree[pos].value=sum[l];
        }else{
            int mid=(l+r)>>1;
            Build(pos<<1,l,mid);
            Build(pos<<1|1,mid+1,r);
            Push_up(pos);
        }
    }

    //单点加
    void Single_Modify(int pos,int x,int v){
        if(Tree[pos].l==x and Tree[pos].r==x){
            Tree[pos].value+=v;
        }else{
            int mid=(Tree[pos].l+Tree[pos].r)>>1;
            if(x<=mid) Single_Modify(pos<<1,x,v);
            else       Single_Modify(pos<<1|1,x,v);
            Push_up(pos);
        }
    }

    //区间加
    void Interval_Modify(int pos,int l,int r,int v){
        if(Tree[pos].l>=l&&Tree[pos].r<=r){
            Tree[pos].value+=v*(Tree[pos].r-Tree[pos].l+1);
            Tree[pos].lazytag+=v;
        }else{
            Push_down(pos);
            int mid=(Tree[pos].l+Tree[pos].r)>>1;
            if(l<=mid) Interval_Modify(pos<<1,l,r,v);
            if(r>mid)  Interval_Modify(pos<<1|1,l,r,v);
            Push_up(pos);
        }
    }

    //区间查询
    long long Query(int pos,int l,int r){
        if(Tree[pos].l>=l&&Tree[pos].r<=r) return Tree[pos].value;
        Push_down(pos);
        int mid=(Tree[pos].l+Tree[pos].r)>>1;
        long long res=0;
        if(l<=mid) res+=Query(pos<<1,l,r);
        if(r>mid)  res+=Query(pos<<1|1,l,r);
        return res;
    }
}Tree;

signed main()
{
	freopen("P1438_2.in","r",stdin);
	freopen("P1438_2.out","w",stdout);
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
		sum[i]=a[i]-a[i-1];
    }Tree.Build(1,1,n);
    for(int i=1;i<=m;i++){
        scanf("%lld",&type);
        if(type==1){
            scanf("%lld%lld%lld%lld",&l,&r,&K,&D);
            Tree.Single_Modify(1,l,K);
			if(l!=r) Tree.Interval_Modify(1,l+1,r,D);
			if(r!=n) Tree.Single_Modify(1,r+1,-(K+(r-l)*D));
        }else{
            scanf("%lld",&p);
            printf("%lld\n",Tree.Query(1,1,p));
        }
    }
    return 0;
}
2023/8/6 12:50
加载中...