CF1136E Nastya Hasn't Written a Legend（线段树）

还能说什么呢，简直太妙了。

$$a_{i+1}<a_i+k_i$$

$$a_{i+1}-k_i-k_{i-1}-\cdots-k_1<a_i+k_i-k_i-k_{i-1}-\cdots-k_1$$

$$a_{i+1}-k_i-k_{i-1}-\cdots-k_1<a_i-k_{i-1}-\cdots-k_1$$

令 $k$ 的前缀和为 $kpre$。

$$a_{i+1}-kpre_i<a_i-kpre_{i-1}$$

令 $b_i=a_i-kpre_{i-1}$。

$$b_{i+1}<b_i$$

也就是 $b$ 应该是单调不降的。

询问，经典操作。注意要加回一些 $kpre$。具体要再开一个 $kpre$ 的前缀和 $kprepre$。

修改，可以线段树上二分，找到最后一个 $\le val$ 的值，区间覆盖即可。

时间复杂度 $O(n+q\log n)$。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=;

const ll INF=9e18;

#define lson o<<1,l,mid

#define rson o<<1|1,mid+1,r

#define FOR(i,a,b) for(int i=(a);i<=(b);i++)

#define ROF(i,a,b) for(int i=(a);i>=(b);i--)

#define MEM(x,v) memset(x,v,sizeof(x))

inline int read(){

    int x=,f=;char ch=getchar();

    while(ch<'' || ch>'') f|=ch=='-',ch=getchar();

    while(ch>='' && ch<='') x=x*+ch-'',ch=getchar();

    return f?-x:x;

}

int n,q,a[maxn],k[maxn];

ll kpre[maxn],kprepre[maxn],b[maxn],sum[maxn*],L[maxn*],R[maxn*],cov[maxn*];

char op[];

inline int pushup(int o){

    sum[o]=sum[o<<]+sum[o<<|];

    L[o]=L[o<<];

    R[o]=R[o<<|];

}

inline void cover(int o,int l,int r,ll x){

    sum[o]=(r-l+)*x;

    L[o]=R[o]=cov[o]=x;

}

inline void pushdown(int o,int l,int r){

    if(cov[o]!=-INF){

        int mid=(l+r)>>;

        cover(lson,cov[o]);

        cover(rson,cov[o]);

        cov[o]=-INF;

    }

}

void build(int o,int l,int r){

    cov[o]=-INF;

    if(l==r) return void(sum[o]=L[o]=R[o]=b[l]);

    pushdown(o,l,r);

    int mid=(l+r)>>;

    build(lson);build(rson);

    pushup(o);

}

ll query(int o,int l,int r,int ql,int qr){

    if(l>=ql && r<=qr) return sum[o];

    pushdown(o,l,r);

    int mid=(l+r)>>;

    ll s=;

    if(mid>=ql) s+=query(lson,ql,qr);

    if(mid<qr) s+=query(rson,ql,qr);

    return s;

}

void update(int o,int l,int r,int p,ll v){

    if(r<p || L[o]>v) return;

    if(l>=p && R[o]<=v) return cover(o,l,r,v);

    pushdown(o,l,r);

    int mid=(l+r)>>;

    update(lson,p,v);update(rson,p,v);

    pushup(o);

}

int main(){

    n=read();

    FOR(i,,n) a[i]=read();

    FOR(i,,n-) k[i]=read();

    FOR(i,,n-) kpre[i]=kpre[i-]+k[i];

    FOR(i,,n-) kprepre[i]=kprepre[i-]+kpre[i];

    FOR(i,,n) b[i]=a[i]-kpre[i-];

    build(,,n);

    q=read();

    while(q--){

        scanf("%s",op+);

        int x=read(),y=read();

        if(op[]=='+') update(,,n,x,query(,,n,x,x)+y);

        else cout<<query(,,n,x,y)+kprepre[y-]-kprepre[max(,x-)]<<endl;

    }

}