线段树0分求调,能过样例
查看原帖
线段树0分求调,能过样例
1160606
OKM_IS楼主2024/7/18 22:24
#include<iostream>
#include<cstdio>
using namespace std;

struct node{
    int L,R;
    long long w,tagd,tagk;
}tree[400005];

int a[100005];

void pushup(int u){
    tree[u].w=tree[u*2].w+tree[u*2+1].w;
}

void build(int u,int c,int d){  
    int m=(c+d)/2;
    tree[u].L=c,tree[u].R=d;
    if(tree[u].L==tree[u].R){
        int x=tree[u].L;
        tree[u].w=a[x];
        return;                  
    }
    build(u*2,c,m);
    build(u*2+1,m+1,d);
    pushup(u);
}

int inrange(int u,int l,int r){
    if(l<=tree[u].L&&r>=tree[u].R)
        return 1;
    else
        return 0;

}

int outrange(int u,int l,int r){
    if(l>tree[u].R||r<tree[u].L)
        return 1;
    else
        return 0;
}

void maketag(int u,long long k,long long d){        //这里的k和d是这个区间实际上要加的k,直接用就行
    tree[u].tagd+=d,tree[u].tagk+=k;
    long long len=tree[u].R-tree[u].L+1;
    tree[u].w+=1ll*len*(k+(len-1)*d+k)/2;

}

void pushdown(int u){
    if(tree[u].tagk==0&&tree[u].tagd==0)
        return;
    long long k=tree[u].tagk,d=tree[u].tagd,m=(tree[u].L+tree[u].R)/2;
    maketag(u*2,k,d);
    maketag(u*2+1,k+m*d,d);
    tree[u].tagk=0,tree[u].tagd=0;
}

long long query(int u,int l,int r){
    if(inrange(u,l,r)){
        return tree[u].w;
    }
    if(outrange(u,l,r)){
        return 0;
    }
    pushdown(u);
    return query(u*2,l,r)+query(u*2+1,l,r);
}

void update(int u,int l,int r,long long k,long long d){
    if(inrange(u,l,r)){
        maketag(u,(tree[u].L-l)*d+k,d);          //使用数据所给的k和d
        return;
    }
    if(outrange(u,l,r)){
        return;
    }
    pushdown(u);
    update(u*2,l,r,k,d);
    update(u*2+1,l,r,k,d);
    pushup(u);

}

int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    build(1,1,n);
    long long op,l,r,k,d;
    while(m--){
        cin>>op;
        //cout<<op;
        if(op==1){
            cin>>l>>r>>k>>d;
            update(1,l,r,k,d);
        }
        else{
            cin>>r;
            cout<<query(1,r,r)<<'\n';
        }

    }
    return 0;
}

2024/7/18 22:24
加载中...