9pts苣蒻求助,实在是看不出问题
查看原帖
9pts苣蒻求助,实在是看不出问题
648772
Liyuqiao11楼主2023/7/16 09:43
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+10;
int n,m,a[N];
struct T{
    int l;
    int r;
    int sum;
}t[N*4];
void pushup(int i){
    t[i].sum=t[i*2].sum+t[i*2+1].sum;
}
void build(int i,int l,int r){
    t[i].l=l;
    t[i].r=r;
    if(l==r){
        t[i].sum=a[l]-a[l-1];
        return;
    }
    int mid=(l+r)/2;
    build(i*2,l,mid);
    build(i*2+1,mid+1,r);
    pushup(i);
}
void update(int i,int l,int r,int d){
    if(t[i].l>=l&&t[i].r<=r){
        t[i].sum+=(t[i].r-t[i].l+1)*d;
        return;
    }
    if(t[i*2].r>=l){
        update(i*2,l,r,d);
    }
    if(t[i*2+1].l<=r){
        update(i*2+1,l,r,d);
    }
    pushup(i);
}
int query(int i,int l,int r){
    if(t[i].l>=l&&t[i].r<=r){
        return t[i].sum;
    }
    int ans=0;
    if(t[i*2].r>=l){
        ans+=query(i*2,l,r);
    }
    if(t[i*2+1].l<=r){
        ans+=query(i*2+1,l,r);
    }
    return ans;
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,1,n);
    for(int i=1;i<=m;i++){
        int op,x,y,k,d;
        cin>>op;
        if(op==1){
            cin>>x>>y>>k>>d;
            int dc=k+(y-x)*d;
            update(1,x,x,k);
            if(x+1<=y&&y<=n)  update(1,x+1,y,d);
            if(y+1<=n) update(1,y+1,y+1,-dc);
        }
        if(op==2){
            cin>>x;
            cout<<query(1,1,x)<<endl;
        }
    }
    return 0;
}
2023/7/16 09:43
加载中...