题目链接：
http://codeforces.com/contest/1136/problem/E
题意：
初始有a数组和k数组
有两种操作，一，求l到r的区间和，二，$a_ipm x$
并且会有一个连锁反应
$$whileleft ( a_{i+1}<a_i+k_i ight )a_{i+1}=a_i+k_i,i++ $$
数据范围：
$2 leq n leq 10^{5}$
$-10^{9} leq a_i leq 10^{9}$
$-10^{6} leq k_i leq 10^{6}$
$1 leq q leq 10^{5}$
$1 leq i leq n$,$0 leq x leq 10^{6}$
$1 leq l leq r leq n$
分析：
对于每次修改，我们可以用二分查找到连锁的末尾。
而对于一个被修改后的区间$(i,r)$的元素$a_x$，它由两部分组成$a_x=a_i+sum_{j=i}^{x-1}k_j$
两部分的值都可以轻易算出，然后用两颗线段树分别记录两部分的区间和（一颗线段树也行）。
用到前缀和的前缀和，还有懒惰标记
具体实现见ac代码
ac代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+10;
const ll INF=1e18;
ll sum1[maxn],sum2[maxn],treea[4*maxn],treeb[4*maxn],lazya[4*maxn],lazyb[4*maxn];
int a[maxn];
void bulida(int l,int r,int rt)
{
int md=(r+l)/2;
if(r==l)
{
treea[rt]=a[l];
return;
}
bulida(l,md,rt*2);
bulida(md+1,r,rt*2+1);
treea[rt]=treea[rt*2]+treea[rt*2+1];
}
void pushdowna(int l,int r,int rt)
{
int md=(l+r)/2;
if(lazya[rt]!=-INF)
{
treea[rt*2]=(md-l+1)*lazya[rt];
treea[rt*2+1]=(r-md-1+1)*lazya[rt];
lazya[rt*2]=lazya[rt*2+1]=lazya[rt];
lazya[rt]=-INF;
}
}
ll quera(int l,int r,int nowl,int nowr,int rt)
{
if(r<nowl||l>nowr)return 0;
int md=(nowr+nowl)/2;
if(l<=nowl&&r>=nowr)return treea[rt];
pushdowna(nowl,nowr,rt);
return quera(l,r,nowl,md,rt*2)+quera(l,r,md+1,nowr,rt*2+1);
}
void updataa(ll x,int l,int r,int nowl,int nowr,int rt)
{
if(r<nowl||l>nowr)return ;
int md=(nowr+nowl)/2;
if(l<=nowl&&r>=nowr)
{
treea[rt]=(nowr-nowl+1)*x;
lazya[rt]=x;
return ;
}
pushdowna(nowl,nowr,rt);
updataa(x,l,r,nowl,md,rt*2);
updataa(x,l,r,md+1,nowr,rt*2+1);
treea[rt]=treea[rt*2]+treea[rt*2+1];
}
void pushdownb(int l,int r,int rt)
{
int md=(l+r)/2;
if(lazyb[rt]!=-INF)
{
treeb[rt*2]=sum2[md-1]-sum2[l-2]+(l-md-1)*sum1[lazyb[rt]-1];
treeb[rt*2+1]=sum2[r-1]-sum2[md+1-2]+(md+1-r-1)*sum1[lazyb[rt]-1];
lazyb[rt*2]=lazyb[rt*2+1]=lazyb[rt];
lazyb[rt]=-INF;
}
}
void updatabb(ll x,int pos,int nowl,int nowr,int rt)
{
int md=(nowr+nowl)/2;
if(nowl==nowr)
{
treeb[rt]=x;
return ;
}
pushdownb(nowl,nowr,rt);
if(pos>=md+1)updatabb(x,pos,md+1,nowr,rt*2+1);
else updatabb(x,pos,nowl,md,rt*2);
treeb[rt]=treeb[rt*2]+treeb[rt*2+1];
}
ll querb(int l,int r,int nowl,int nowr,int rt)
{
if(r<nowl||l>nowr)return 0;
int md=(nowr+nowl)/2;
if(l<=nowl&&r>=nowr)return treeb[rt];
pushdownb(nowl,nowr,rt);
return querb(l,r,nowl,md,rt*2)+querb(l,r,md+1,nowr,rt*2+1);
}
void updatab(ll x,int l,int r,int nowl,int nowr,int rt)
{
if(r<nowl||l>nowr)return ;
int md=(nowr+nowl)/2;
if(l<=nowl&&r>=nowr)
{
treeb[rt]=sum2[nowr-1]-sum2[nowl-2]+(nowl-nowr-1)*sum1[x-1];
lazyb[rt]=x;
return ;
}
pushdownb(nowl,nowr,rt);
updatab(x,l,r,nowl,md,rt*2);
updatab(x,l,r,md+1,nowr,rt*2+1);
treeb[rt]=treeb[rt*2]+treeb[rt*2+1];
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1; i<=n; i++)
scanf("%d",&a[i]);
for(int i=1; i<=n-1; i++)
{
int x;
scanf("%d",&x);
sum1[i]=sum1[i-1]+x;
sum2[i]=sum2[i-1]+sum1[i];
}
for(int i=0; i<4*maxn; i++)lazya[i]=lazyb[i]=-INF;
bulida(1,n,1);
int T;
scanf("%d",&T);
while(T--)
{
getchar();
char key;
scanf("%c",&key);
if(key=='s')
{
int l,r;
scanf("%d %d",&l,&r);
printf("%lld
",quera(l,r,1,n,1)+querb(l,r,1,n,1));
}
else if(key=='+')
{
ll x,add;
scanf("%lld %lld",&x,&add);
add=quera(x,x,1,n,1)+querb(x,x,1,n,1)+add;
int st=x,en=n;
while(st!=en)
{
int md=(st+en)/2;
if(sum1[md+1-1]-sum1[x-1]+add>=querb(md+1,md+1,1,n,1)+quera(md+1,md+1,1,n,1))st=md+1;
else en=md;
}
updataa(add,x,st,1,n,1);
updatab(x,x+1,st,1,n,1);
updatabb(0,x,1,n,1);
}
}
return 0;
}