CF1136E Nastya Hasn‘t Written a Legend

$Result$

$Hyperlink$

https://www.luogu.com.cn/problem/CF1136E

$Description$

给定一个长度为$n$的数组$a$和长度为$n-1$的数组$k$，$m$次询问
包含两种操作

1. $a_x+=y$，同时若加完之后$a_{i+1}<a_i+a_k$，则令$a_{i+1}=a_i+a_k$，同时继续判断$a_{i+2}<更新后的a_{i+1}+a_{k+1}$，然后赋值$a_{i+2}=更新后的a_{i+1}+a_{k+1}$，以此类推，直到不合法为止
2. 查询$a[x\sim y]$的和

数据范围：$n,m\le 10^5,|a_i|,|k_i|\le 10^9$

$Solution$

考虑什么时候满足题目所述条件
$a_i\ge a_{i-1}+k_{i-1}\ge a_{i-2}+k_{i-2}+k_{i-1}\ge a_j+{\sum }_{l=j}^{i-1}{k}_l|j<i$

令$g_i={\sum }_{j=1}^i{k}_i$

则$a_i\ge a_1+g_{i-1}$，貌似有用，但因为$k_i$可以是负数，所以不是很有用

但我们可以让$u_i=a_i-g_{i-1}$
由$a_i\ge a_{i-1}+k_{i-1}$得
$a_i-g_{i-1}\ge a_{i-1}-g_{i-2}+k_{i-1}$
则
$u_i\ge u_{i-1}$

即$u_i$单调不降，所以我们可以用线段树维护一个$u_i$

对于修改操作，只需二分一个断点，然后区间赋值
对于查询操作，只需要查询区间$u_i$的和，然后补上多减的$g$，后者可以预处理$g$的前缀和实现

时间复杂度：$O(n\log n)$

$Code$

#include<cctype>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
#define N 100010
using namespace std;int n,m;
LL a[N],k[N],g[N],x,y,s[N];
char op[10];
struct xds 
{#define lson k<<1#define rson k<<1|1#define mid (l+r>>1)#define gol lson,l,mid#define gor rson,mid+1,rLL dat[N<<2],lzy[N<<2];inline void build(int k=1,int l=1,int r=n){lzy[k]=-9e18;if(l==r) return (void)(dat[k]=a[l]-g[l-1]);build(gol);build(gor);return (void)(dat[k]=dat[lson]+dat[rson]);}inline void reset(int k,int l,int r,LL x){return (void)(lzy[k]=x,dat[k]=(r-l+1)*x);}inline void pushdown(int k,int l,int r){if(lzy[k]!=-9e18) reset(gol,lzy[k]),reset(gor,lzy[k]),lzy[k]=-9e18;return;}inline LL Query(int ql,int qr,int k=1,int l=1,int r=n){if(l>qr||r<ql) return 0;if(ql<=l&&qr>=r) return dat[k];pushdown(k,l,r);return Query(ql,qr,gol)+Query(ql,qr,gor);}inline void Modify(int ql,int qr,LL x,int k=1,int l=1,int r=n){if(l>qr||r<ql) return;if(ql<=l&&qr>=r) return (void)(reset(k,l,r,x));pushdown(k,l,r);Modify(ql,qr,x,gol);Modify(ql,qr,x,gor);return (void)(dat[k]=dat[lson]+dat[rson]);}#undef lson#undef rson#undef mid#undef gol#undef gor
}T;
inline LL read()
{char c;LL d=1,f=0;while(c=getchar(),!isdigit(c)) if(c=='-') d=-1;f=(f<<3)+(f<<1)+c-48;while(c=getchar(),isdigit(c)) f=(f<<3)+(f<<1)+c-48;return d*f;
}
signed main()
{n=read();for(register int i=1;i<=n;i++) a[i]=read();for(register int i=1;i<n;i++) g[i]=g[i-1]+read(),s[i]=s[i-1]+g[i];T.build();m=read();while(m--){scanf("%s",op);x=read();y=read();if(op[0]=='s') printf("%lld\n",T.Query(x,y)+s[max(0ll,y-1)]-s[max(0ll,x-2)]);else{int l=x,r=n,mid;LL v=T.Query(x,x)+y;while(l<=r){int mid=l+r>>1;LL k=T.Query(mid,mid);if(k==v) break;if(k>v) r=mid-1;else l=mid+1;}T.Modify(x,l+r>>1,v);}}
}