我们发现,如果我们把 \(\sum_{j<i}k_j\) 从 \(a_i\) 里面去掉,那么剩下的 \(a_i\) 就很好搞。
因为,设 \(b_i=a_i-\sum_{j<i}k_j\),那么 \(a_i+k_i> a_{i+1}\) 就变成 \(b_i>b_{i+1}\)。从一个奇怪的递推关系变成了很好的偏序关系。而且我们由此知道序列在任何时候是有序的。
所以,我们把 \(a_i-\sum_{j<i}k_j\) 单独拿出来维护。我们需要实现的就是维护一个有序序列,每次找到一个位置,加上一个数,然后把后面所有小于它的都变成它。维护 \(b_i\) 区间和,对 \(k_j\) 的前缀和作前缀和即可。而实际上我们只需要一棵线段树实现区间修改和区间和查询。
最终的问题只剩下如何找到要修改的区间。第一个思路是二分。因为后面的部分是有序的,所以我们可以二分最后一个小于等于它的位置。但是这样存在一个问题,就是我们不能快速得知当前位置的值,不管用什么方法,set
也好,线段树也好,都带一个 \(\log\),导致 \(\log^2\) 成为复杂度瓶颈,虽然也能过,但不是好方法。
考虑用 set
维护所有 \(b\) 相同的连续段。
我们发现,对于一段 \(b\) 相同的来说,要么都修改,要么都不修改。因为它们是相同的。
而我们每次往后查找的时候,遇到一个不需要修改的就可以停下了,因为序列是单调的。
这样就很好搞了,我们用 set
维护所有连续段,每次修改的时候,就把当前值所在的连续段断开,然后一路查找所有被更新的段,合并起来,同时也得到了修改区间,在线段树上修改即可。
复杂度 \(O(n\log n)\)。
ll n,q,a[100005],b[100005],s[100005],ss[100005],x,y;
struct node{
ll l,r,tg,s;
}sg[400005];
char c;
inline void init(int i,int l,int r){
sg[i].l=l,sg[i].r=r,sg[i].s=0,sg[i].tg=-1e18;
if(l==r){
sg[i].s=a[sg[i].l];
return;
}init(i<<1,l,(l+r)>>1);
init(i<<1|1,((l+r)>>1)+1,r);
sg[i].s=(sg[i<<1].s+sg[i<<1|1].s);
}
inline void push(int i){
if(sg[i].tg==-1e18)return;
sg[i].s=sg[i].tg*(sg[i].r-sg[i].l+1);
if(sg[i].l!=sg[i].r){
sg[i<<1].tg=sg[i].tg;
sg[i<<1|1].tg=sg[i].tg;
}sg[i].tg=-1e18;
}
inline void add(int i,int l,int r,ll v){
push(i);
if(sg[i].l>r||sg[i].r<l)return;
if(sg[i].l>=l&&sg[i].r<=r){
sg[i].tg=v;
return push(i);
}add(i<<1,l,r,v);
add(i<<1|1,l,r,v);
sg[i].s=(sg[i<<1].s+sg[i<<1|1].s);
}
inline ll qry(int i,int l,int r){
push(i);
if(sg[i].l>r||sg[i].r<l)return 0;
if(sg[i].l>=l&&sg[i].r<=r){
return sg[i].s;
}ll res=qry(i<<1,l,r)+qry(i<<1|1,l,r);
sg[i].s=(sg[i<<1].s+sg[i<<1|1].s);
return res;
}
struct nd{
ll l,r,v;
bool operator <(const nd b)const{
return l<b.l;
}
};
set<nd>se;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
rp(i,n)cin>>a[i];
rep(i,2,n)cin>>b[i];
rp(i,n)s[i]=s[i-1]+b[i];
rp(i,n)a[i]-=s[i];
init(1,1,n);
rp(i,n)ss[i]=ss[i-1]+s[i];
rp(i,n)se.insert({i,i,a[i]});
cin>>q;
rp(i,q){
cin>>c>>x>>y;
if(c=='+'){
int l=x,r=x;
auto k=se.upper_bound({x,0,0});k--;
r=k->r;
ll fl=k->l,fk=k->v;
se.erase(k);
if(fl<x)se.insert({fl,x-1,fk});
k=se.upper_bound({x,0,0});
while(k!=se.end()&&k->v<fk+y){
r=k->r;se.erase(k);
k=se.upper_bound({x,0,0});
}add(1,l,r,fk+y);
se.insert({l,r,fk+y});
}else{
cout<<qry(1,x,y)+ss[y]-ss[x-1]<<endl;
}
}
return 0;
}
//Nyn-siyn-hert