题目大意：NOIP2018d1t1 支持 M 次区间查询答案和区间修改操作。
题解：
首先考虑不带区间修改的情况。从左到右进行考虑，发现对于第 i 个数来说，对答案的贡献仅仅取决于第 i-1 个数的大小：若 (a_i le a_{i-1})，则第 i 个数对答案的贡献为 0，否则对答案的贡献为两者的差值。贡献可以这样算是因为每个点至少增加 (a_i) 次，且当前点增加多少仅对后面一个数有直接影响。因此，考虑维护差分数组即可，区间修改变成两次单点修改，区间查询转变成查询区间大于 0 的数字之和。则每次询问 [l,r] 的答案为：sum[l+1,r] + a[l]，a[l] 利用树状数组维护差分序列即可单点回答了。时间复杂度为 (O(MlogN))。
代码如下
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=1e5+10;
typedef long long LL;
int n,m,a[maxn],d[maxn];
LL bit[maxn];
void update(int pos,LL val){
for(int i=pos;i<=n;i+=i&-i)bit[i]+=val;
}
LL get(int pos){
LL ret=0;
for(int i=pos;i;i-=i&-i)ret+=bit[i];
return ret;
}
struct node{
#define ls(o) t[o].lc
#define rs(o) t[o].rc
int lc,rc;LL sum;
}t[maxn<<1];
int tot,rt;
void up(int o){
LL suml=t[ls(o)].sum>=0?t[ls(o)].sum:0;
LL sumr=t[rs(o)].sum>=0?t[rs(o)].sum:0;
t[o].sum=suml+sumr;
}
void build(int &o,int l,int r){
o=++tot;
if(l==r){t[o].sum=d[l];return;}
int mid=l+r>>1;
build(ls(o),l,mid),build(rs(o),mid+1,r);
up(o);
}
void modify(int o,int l,int r,int pos,int val){
if(l==r){t[o].sum+=val;return;}
int mid=l+r>>1;
if(pos<=mid)modify(ls(o),l,mid,pos,val);
else modify(rs(o),mid+1,r,pos,val);
up(o);
}
LL query(int o,int l,int r,int x,int y){
if(l==x&&r==y)return max(t[o].sum,0LL);
int mid=l+r>>1;
if(y<=mid)return query(ls(o),l,mid,x,y);
else if(x>mid)return query(rs(o),mid+1,r,x,y);
else return query(ls(o),l,mid,x,mid)+query(rs(o),mid+1,r,mid+1,y);
}
void read_and_parse(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=2;i<=n;i++)d[i]=a[i]-a[i-1];
build(rt,1,n);
}
void solve(){
int opt,l,r,val;
while(m--){
scanf("%d",&opt);
if(opt==1){
scanf("%d%d%d",&l,&r,&val);
modify(rt,1,n,l,val),update(l,val);
if(r!=n)modify(rt,1,n,r+1,-val),update(r+1,-val);
}else{
scanf("%d%d",&l,&r);
LL ret=l==r?0:query(rt,1,n,l+1,r);
printf("%lld
",ret+get(l)+a[l]);
}
}
}
void init(){
tot=rt=0;
for(int i=1;i<=n;i++)bit[i]=0;
}
int main(){
int T;
scanf("%d",&T);
while(T--){
init();
read_and_parse();
solve();
}
return 0;
}