线段树+等差区间求和9ts,求调
查看原帖
线段树+等差区间求和9ts,求调
723554
cfl123楼主2023/10/29 21:39
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
ll n,m,a[100001];
struct L{
    ll l,r;
    ll k,d,val;
}t[400001];
void build(ll p,ll l,ll r){ //建树
    t[p].l=l,t[p].r=r;
    if(l==r){
        t[p].val=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(2*p,l,mid);
    build(2*p+1,mid+1,r);
}
void spread(ll p){ //懒标记
    ll lSum=t[p*2].r-t[p*2].l+1,rSum=t[p*2+1].r-t[p*2+1].l+1;
    t[p*2].val+=(lSum*t[p].k+lSum*(lSum-1)/2*t[p].d);//左区间等差
    t[p*2+1].val+=(rSum*(t[p].k+lSum*t[p].d)+(rSum)*(rSum-1)/2*t[p].d);//右区间首项k=k+d*左区间长度
    t[2*p].k+=t[p].k,t[2*p].d+=t[p].d;
    t[2*p+1].k+=(lSum*t[p].d+t[p].k),t[2*p+1].d+=t[p].d;//右区间首项k=k+d*左区间长度
    t[p].k=0,t[p].d=0;
}
void add(ll p,ll x,ll y,ll k,ll d){ //
    if(x<=t[p].l&&y>=t[p].r){
        t[p].k+=k,t[p].d+=d;
        ll N=t[p].r-t[p].l+1;
        t[p].val+=(N*k+N*(N-1)/2*d);
        return;
    }
    spread(p);
    ll mid=(t[p].l+t[p].r)>>1;
    if(x>mid) add(2*p+1,x,y,k,d);
    if(x<=mid) add(2*p,x,y,k,d);
    if(y>mid&&x<=mid) add(2*p+1,x,y,k+(mid-x+1)*d,d);//左右区间都有,需考虑右区间k
}
ll ask(ll p,ll x,ll y){ //输出
    if(x<=t[p].l&&y>=t[p].r){
        return t[p].val;
    }
    spread(p);
    ll mid=(t[p].l+t[p].r)>>1,sum=0;
    if(x<=mid) sum+=ask(2*p,x,y);
    if(y>mid) sum+=ask(2*p+1,x,y);
    return sum;
}
int main(){
    cin>>n>>m;
    for (ll i=1;i<=n;++i)cin>>a[i];
    build(1,1,n);
    for (ll i=0;i<m;++i){
        ll p,x,y,k,d;
        cin>>p;
        if(p==1){
            cin>>x>>y>>k>>d;
            add(1,x,y,k,d);
        }
        else cin>>x,cout<<ask(1,x,x)<<endl;
    }
    return 0;
}
2023/10/29 21:39
加载中...