Description
属于小Q管辖的n座摩天楼从左往右排成一排，编号依次为1到n，第i座摩天楼的高度为h_i。小Q会进行m次以下两种
操作之一：
2 l r，询问h_l+h_{l+1}+...+h_r。
1 l r，对于第l到r的每座摩天楼i，如果上次操作结束时h_i<h_{i-1}，则将第i座摩天楼再往上造一层，即h_i增加1。
你可以认为h_0=正无穷。
请写一个程序回答小Q的每个询问。
Input
第一行包含两个正整数n,m(1<=n<=100000,1<=m<=min(100000,2n))，分别表示摩天楼的数量以及操作的数量。
第二行包含n个正整数h_1,h_2,...,h_n(1<=h_i<=n)，表示每座楼的高度。
接下来m行，每行三个正整数op,l,r(1<=op<=2,1<=l<=r<=n)，分别表示每个操作。
因为小Q觉得错乱不齐的建筑更加美观，因此你可以认为数据是完全随机的。
Output
对于每个询问输出一行一个整数，即区间内所有摩天楼的高度之和。
可以发现对随机数据$h_i-h_{i-1}<0$的变化次数是O(n)的，因此可以用线段树维护操作，注意特判区间端点。维护区间内h的和，再记一些信息表示再操作几次$h_i-h_{i-1}<0$会出现变化，当出现变化时暴力修改。时间复杂度O(nlogn)。
#include<bits/stdc++.h>
typedef long long i64;
const int N=1e5+,inf=1e8;
char ib[N*],*ip=ib;
int _(){
int x=;
while(*ip<)++ip;
while(*ip>)x=x*+*ip++-;
return x;
}
int n,m,h[N],d[N],_l,_r;
i64 _s;
inline int min(int a,int b){return a<b?a:b;}
inline int max(int a,int b){return a>b?a:b;}
struct node;
node*at(int x);
struct node{
node*lc,*rc;
int L,R,M,a,sz,v1,v2,v3,cd,dd;
i64 s;
void add(int x){
a+=x;
s+=sz*i64(x);
v1+=x,v2-=x;
if(!M)v3+=dd*x;
}
void dn(){
if(a)lc->add(a),rc->add(a),a=;
}
void set(int x,int y){
sz=d[L];
v1=(x<&&y==)?x:-inf;
v2=(x>=&&y==-)?x:inf;
v3=x;
dd=y;
}
void init(){
s=h[L];
set(h[L]-h[L-],d[L]-d[L-]);
}
void up(){
s=lc->s+rc->s;
sz=lc->sz+rc->sz;
v1=max(lc->v1,rc->v1);
v2=min(lc->v2,rc->v2);
cd=lc->cd||rc->cd;
}
void addl(){
if(M)dn(),(_l<=M?lc:rc)->addl(),up();
else{
cd=(!++v3);
++s,++v1,++v2;
}
}
void addr(){
if(M)dn(),(_r<=M?lc:rc)->addr(),up();
else{
cd=(!v3--);
--v1,--v2;
}
}
void add(){
if(_l<=L&&R<=_r)return add();
dn();
if(_l<=M)lc->add();
if(_r>M)rc->add();
up();
}
void sum(){
if(_l<=L&&R<=_r)return void(_s+=s);
dn();
if(_l<=M)lc->sum();
if(_r>M)rc->sum();
}
bool ir(){
return v1>=||v2<||cd;
}
void chk2(){
if(M)dn(),(_l<=M?lc:rc)->chk2(),up();
else{
if(ir()){
_l=L+;
d[L]^=;
cd=;
}else _l=n+;
set(v3,d[L]-d[L-]);
}
}
void chk(){
if(M)dn(),(lc->ir()?lc:rc)->chk(),up();
else{
_l=L+;
d[L]^=;
cd=;
set(v3,d[L]-d[L-]);
}
}
}ns[N*],*np=ns,*rt;
node*at(int x){
node*w=rt;
while(w->M){
w->dn();
w=x<=w->M?w->lc:w->rc;
}
return w;
}
node*build(int L,int R){
node*w=np++;
w->L=L,w->R=R;
if(L<R){
int M=w->M=(L+R)>>;
w->lc=build(L,M);
w->rc=build(M+,R);
w->up();
}else w->init();
return w;
}
int main(){
fread(ib,,sizeof(ib),stdin);
n=_(),m=_();
h[]=inf;
for(int i=;i<=n;++i)h[i]=_(),d[i]=h[i]<h[i-];
rt=build(,n);
for(int o;m;--m){
o=_(),_l=_(),_r=_();
if(o==){
if(d[_l])rt->addl();
if(_r<n&&d[_r])++_r,rt->addr(),--_r;
if(++_l<=_r)rt->add();
while(rt->ir())for(rt->chk();_l<=n;rt->chk2()); }else{
_s=;
rt->sum();
printf("%lld\n",_s);
}
}
return ;
}