线段树过134,其余re
查看原帖
线段树过134,其余re
1165199
gmjgmjgmj楼主2024/3/10 20:23
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=5e5+10;
int a[maxn];
int n,m;

struct segment
{
    int l,r,sum,mark;
}tr[maxn*4];

inline void build(int i,int l,int r)
{
    tr[i].l=l;
    tr[i].r=r;
    if(l==r)
    {
        tr[i].sum=a[l];
        return;
    }
    int mid=l+r>>1;
    build(i<<1,1,mid);
    build(i<<1|1,mid+1,r);
    tr[i].sum=tr[i<<1].sum+tr[i<<1|1].sum;
    return;
}

inline void f(int i,int k)
{
    tr[i].mark+=k;
    tr[i].sum+=k*(tr[i].r-tr[i].l+1);
}

inline void pushdown(int i)
{
    f(i<<1,tr[i].mark);
    f(i<<1|1,tr[i].mark);
    tr[i].mark=0;
}

inline void add(int i,int l,int r,int k)
{
    if(tr[i].l>=l and tr[i].r<=r)
    {
        tr[i].sum+=(tr[i].r-tr[i].l+1)*k;
        tr[i].mark+=k;
        return;
    }
    pushdown(i);
    int mid=(tr[i].l+tr[i].r)>>1;
    if(l<=mid)
        add(i<<1,l,r,k);
    if(r>mid)
        add(i<<1|1,l,r,k);
    tr[i].sum=tr[i<<1].sum+tr[i<<1|1].sum;
    return;
}

inline int search(int i,int x)
{
    if(tr[i].l==tr[i].r)
        return tr[i].sum;
    pushdown(i);
    int mid=(tr[i].l+tr[i].r)>>1;
    if(x<=mid)
        return search(i<<1,x);
    if(x>mid)
        return search(i<<1|1,x);
}

inline void solve()
{
    int is,x,y,k;
    cin>>is;
    if(is==1)
    {
        cin>>x>>y>>k;
        add(1,x,y,k);
        return;
    }
    else
    {
        cin>>x;
        int ans=search(1,x);
        cout<<ans<<"\n";
        return;
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    build(1,1,n);
    while(m--)
        solve();
    return 0;
}
2024/3/10 20:23
加载中...