正文
【bzoj5050】【bzoj九月月赛H】建造摩天楼
小程序：扫一扫查出行【扫一扫了解最新限行尾号】
复制小程序
讲个笑话，这个题很休闲的。
大概是这样的，昨天看到这个题，第一眼星际把题目看反了然后感觉这是个傻逼题。
后来发现不对，这个修改一次的影响是很多的，可能导致一个数突然可以被改，也可能导致一个数不能被改。
大概就是一个不断拔高，最后拔得跟区间最大值一样高的过程。
后来开始想做法，感觉是不是可以维护一下最小的深度差，然后这个以内直接加，超过了就重构？
感觉似乎有点道理，写写写
自己想又感觉这个不太靠谱，可能会重构上天，然后就删了。
（flag++）
然后问了栋老师，栋老师一眼星际（跟我下午一样），然后忙着写集训队作业去了。
（天下神犇都神的相似，傻逼各有各的傻法）
后来问了lxl，挂张图：
他说的似乎有点道理，然而我没太弄懂他想表达什么
于是GG看其他题目去了。。。。。。
后来看了题解……
mdzz这不是我下午想的那个吗……？
然后想了下这个随机期望的复杂度，不太会，问了下栋老师，大概得到的结果是这样的：
首先分类讨论。
所以重构会在常数次，因此题解的复杂度是正确的~
然后谈一下维护：
由于变化会影响左右两边，所以维护一下左右两边的最小深度，每次在线段树上收集重构节点，大力计算就好。
#include<bits/stdc++.h>
#define lson (o<<1)
#define rson (o<<1|1)
const int N=;
const int inf=;
typedef long long ll;
inline int min(int x,int y){return x<y?x:y;}
using namespace std;
int n,m,a[N],exis[N],exl[N],exr[N],cnt,q[N];
ll sumv[N<<];int addv[N<<],minl[N<<],minr[N<<],size[N<<];
const int ch_top=4e7+;
typedef long long ll;
char ch[ch_top],*now_r=ch-,*now_w=ch-;
inline int read(){
while(*++now_r<'');
register int x=*now_r-'';
while(*++now_r>='')x=x*+*now_r-'';
return x;
}
inline void write(ll x){
static char st[];static int top;
while(st[++top]=''+x%,x/=);
while(*++now_w=st[top],--top);
*++now_w='\n';
}
inline void pushup(int o){
minr[o]=min(minr[lson],minr[rson]);
minl[o]=min(minl[lson],minl[rson]);
}
inline void puttag(int o,int v){
sumv[o]+=v*size[o];addv[o]+=v;minl[o]-=v;minr[o]-=v;
}
inline void pushdown(int o){
if(!addv[o])return;
puttag(lson,addv[o]);puttag(rson,addv[o]);
addv[o]=;
}
inline void build(int o,int l,int r){
if(l==r){
sumv[o]=a[l];size[o]=exis[l];minl[o]=exl[l];minr[o]=exr[l];
return;
}
int mid=(l+r)>>;
build(lson,l,mid);build(rson,mid+,r);
pushup(o);
sumv[o]=sumv[lson]+sumv[rson];
size[o]=size[lson]+size[rson];
}
inline void recalc(int o,int l,int r,int q){
if(l==r){
if(exis[l])a[l]+=addv[o];
addv[o]=;return;
}
pushdown(o);
int mid=(l+r)>>;
if(q<=mid)recalc(lson,l,mid,q);else recalc(rson,mid+,r,q);
}
inline ll querysum(int o,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr)return sumv[o];
pushdown(o);
int mid=(l+r)>>;ll ans=;
if(ql<=mid)ans+=querysum(lson,l,mid,ql,qr);
if(qr>mid)ans+=querysum(rson,mid+,r,ql,qr);
return ans;
}
inline void change(int o,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr)return void(puttag(o,));
pushdown(o);int mid=(l+r)>>;
if(ql<=mid)change(lson,l,mid,ql,qr);
if(qr>mid)change(rson,mid+,r,ql,qr);
pushup(o);
sumv[o]=sumv[lson]+sumv[rson];
}
inline void recexi(int o,int l,int r,int q){
if(l==r){
size[o]=exis[l];minl[o]=exl[l];minr[o]=exr[l];
return;
}
pushdown(o);int mid=(l+r)>>;
if(q<=mid)recexi(lson,l,mid,q);else recexi(rson,mid+,r,q);
pushup(o);
size[o]=size[lson]+size[rson];
}
inline void recml(int o,int l,int r,int q,int v){
if(l==r){minl[o]=v;return;}
pushdown(o);int mid=(l+r)>>;
if(q<=mid)recml(lson,l,mid,q,v);else recml(rson,mid+,r,q,v);
minl[o]=min(minl[lson],minl[rson]);
}
inline void recmr(int o,int l,int r,int q,int v){
if(l==r){minr[o]=v;return;}
pushdown(o);int mid=(l+r)>>;
if(q<=mid)recmr(lson,l,mid,q,v);else recmr(rson,mid+,r,q,v);
minr[o]=min(minr[lson],minr[rson]);
}
inline void dfs(int o,int l,int r){
if(minl[o]>&&minr[o]>=)return;
if(l==r){
if(minl[o]<=&&q[cnt]!=l)q[++cnt]=l;
if(minr[o]<)q[++cnt]=l+;
return;
}
pushdown(o);int mid=(l+r)>>;
dfs(lson,l,mid);dfs(rson,mid+,r);
}
inline bool flag(int i){return a[i-]>a[i];}
inline int calcl(int i){return exis[i]&&!exis[i-]?a[i-]-a[i]:inf;}
inline int calcr(int i){return exis[i]&&!exis[i+]?a[i+]-a[i]:inf;}
inline void calcexl(int i){if(i<||i>n)return;recml(,,n+,i,calcl(i));}
inline void calcexr(int i){if(i<||i>n)return;recmr(,,n+,i,calcr(i));}
inline void get(int i){if(i<||i>n)return;recalc(,,n+,i);}
inline void qwq(int i){
if(i<||i>n)return;get(i);get(i-);get(i+);exis[i]=flag(i);exl[i]=calcl(i);exr[i]=calcr(i);
recexi(,,n+,i);calcexl(i+);calcexr(i-);
}
int main(){
fread(ch,,ch_top,stdin);
n=read();m=read();
a[]=exl[]=exr[]=inf;a[n+]=exl[n+]=exr[n+]=inf;
for(int i=;i<=n;i++)a[i]=read(),exis[i]=flag(i);
for(int i=;i<=n;i++)exl[i]=calcl(i),exr[i]=calcr(i);
build(,,n+);
while(m--){
int opt=read(),x=read(),y=read();
if(opt==){
cnt=;change(,,n+,x,y);dfs(,,n+);
for(int i=;i<=cnt;i++)qwq(q[i]);
qwq(x);qwq(y+);
}
else{
write(querysum(,,n+,x,y));
}
}
fwrite(ch,,now_w-ch,stdout);
}
