线段树RE求调
查看原帖
线段树RE求调
623219
StrSeeker楼主2023/10/18 00:23
#include<cstdio>
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
const int maxn = 5e5+5;
struct segment_tree
{
    int l,r,value;
}tr[maxn*4];
int a[maxn];
int add[maxn*4];
void Pushup(int p)
{
    tr[p].value=tr[p*2].value+tr[p*2+1].value;
}
void Pushdown(int p)
{
    if(add[p]!=0)
    {
        tr[p*2].value+=add[p]*(tr[p*2].r-tr[p*2].l+1);
        tr[p*2+1].value+=add[p]*(tr[p*2+1].r-tr[p*2+1].l+1);
        add[p*2]+=add[p];
        add[p*2+1]+=add[p];
        add[p]=0;
    }
}
void build(int pos,int l,int r)
{
    tr[pos].l=l;
    tr[pos].r=r;
    if(l==r)
    {
        tr[pos].value=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(pos*2,l,mid);
    build(pos*2+1,mid+1,r);
    Pushup(pos);
}
void update(int pos,int l,int r,int k)
{
    if(l<=tr[pos].l && r>=tr[pos].r)
    {
        add[pos]+=k;
        tr[pos].value+=(long long)k*(tr[pos].r-tr[pos].l+1);
        return;
    }
//    if(l>tr[pos].r || r<tr[pos].l) return;
    Pushdown(pos);
    int mid=(l+r)>>1;
    if(l<=mid) update(pos*2,l,r,k);
    if(r>mid) update(pos*2+1,l,r,k);
    Pushup(pos);
}
int query(int pos,int rk)
{
    if(tr[pos].l==tr[pos].r)
    {
        return tr[pos].value;
    }
    Pushdown(pos);
    if(rk<=tr[pos*2].r) return query(pos*2,rk);
    else return query(pos*2+1,rk);
}
signed main()
{
//    int n,m;
    scanf("%lld %lld",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        int op;
        scanf("%lld",&op);
        if(op==1)
        {
            int l,r,k;
            scanf("%lld %lld %lld",&l,&r,&k);
            update(1,l,r,k);
        }
        else
        {
            int kk;
            scanf("%lld",&kk);
            printf("%lld\n",query(1,kk));
        }
    }
}
2023/10/18 00:23
加载中...