洛谷
代码比较复杂，但是实际上所有操作难度其实都不是很高。
首先考虑操作 \(0\) 怎么做，不难发现我们其实就是需要把这个位置旁边且中间没有高度大于 \(h\) 的地方的高度都设置为 \(h\)。
那么就需要先找到修改的范围，然后进行区间修改。
显然可以使用线段树，在线段树上每个节点维护墙的高度，然后在上面进行二分。
锁定了范围之后，再进行修改即可。
然后操作 \(2\) 也比较简单了，由于高度只会增加，所以每个位置高度不会发生改变，直接修改在线段树上记录的高度即可。
操作 \(3\) 由于是单点查询，所以直接向下找到对应的点查询即可。
最困难的就是操作 \(1\) 该如何实现放水操作。
思考一下放水以后会发生什么变化。
可以发现，一个位置的变化后变成了到放水位置中间最高的墙的高度，不过如果没有那么高的话就不变了。
考虑如何在线段树上进行此操作。
由于具有不同方向，我们考虑使用两个不同的标记数组来标记修改的大小。
我们选择一个方向在线段树上进行处理，记录途中经过的墙的最大高度，同时给一个点打上前面墙高度的标记。
那么在最后，就只需要把加水的标记结果和左边放水和右边放水的结果取最小值即可。
剩下来唯一的难点是怎样实现不同方向放水的标记下传。
由于是单点查询，我们只在每个节点记录前面的内容，在下传时再考虑分开后后面一边墙的高度即可。
对于排水的标记，之前得到的水位高度和前面墙的高度取最小值即可计算。
然后在下传标记之前进行可持久化，重新记录一个新节点即可完成本题。
代码：
#include<bits/stdc++.h>
using namespace std;
int read(){char c=getchar();int x=0;bool f=0;while(c>'9'||c<'0'){if(c=='-')f=1;c=getchar();}while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();if(f)return -x;return x;
}
const int inf=2e9;
int n,q,h[200005],rt[200005];
struct P{int hl,hr,v,tagl,tagr;
};
struct ST{P c[60000005];int ls[60000005],rs[60000005],id;int New(int x){id++;c[id]=c[x];ls[id]=ls[x];rs[id]=rs[x];return id;}void pushup(int p){c[p].hl=max(c[ls[p]].hl,c[rs[p]].hl);c[p].hr=max(c[ls[p]].hr,c[rs[p]].hr);}int build(int l,int r){int p=++id;c[p].v=-inf;c[p].tagl=c[p].tagr=inf;if(l==r){c[p].hl=h[l];c[p].hr=h[l+1];c[p].v=0;return p;}int mid=l+r>>1;ls[p]=build(l,mid);rs[p]=build(mid+1,r);pushup(p);return p;}void pushdown(int p){ls[p]=New(ls[p]),rs[p]=New(rs[p]);c[ls[p]].tagl=min(max(c[ls[p]].tagl,c[p].v),c[p].tagl);c[rs[p]].tagl=min(max(c[rs[p]].tagl,c[p].v),max(c[p].tagl,c[ls[p]].hr));c[ls[p]].tagr=min(max(c[ls[p]].tagr,c[p].v),max(c[p].tagr,c[rs[p]].hl));c[rs[p]].tagr=min(max(c[rs[p]].tagr,c[p].v),c[p].tagr);c[ls[p]].v=max(c[ls[p]].v,c[p].v);c[rs[p]].v=max(c[rs[p]].v,c[p].v);c[p].v=-inf;c[p].tagl=c[p].tagr=inf;}int queryl(int p,int l,int r,int w,int v){if(l==r){if(c[p].hl>=v)return l;return 0;}int mid=l+r>>1;if(w<=mid)return queryl(ls[p],l,mid,w,v);if(r<=w){if(c[rs[p]].hl>=v)return queryl(rs[p],mid+1,r,w,v);return queryl(ls[p],l,mid,w,v);}int tmp=queryl(rs[p],mid+1,r,w,v);if(!tmp)tmp=queryl(ls[p],l,mid,w,v);return tmp;}int queryr(int p,int l,int r,int w,int v){if(l==r){if(c[p].hl>=v)return l;return 0;}int mid=l+r>>1;if(w>mid)return queryr(rs[p],mid+1,r,w,v);if(l>=w){if(c[ls[p]].hl>=v)return queryr(ls[p],l,mid,w,v);return queryr(rs[p],mid+1,r,w,v);}int tmp=queryr(ls[p],l,mid,w,v);if(!tmp)tmp=queryr(rs[p],mid+1,r,w,v);return tmp;}void change(int p,int l,int r,int L,int R,int v,int op){if(l>=L&&r<=R){if(op==0){c[p].tagl=max(c[p].tagl,v);c[p].tagr=max(c[p].tagr,v);c[p].v=max(c[p].v,v); }else if(op==1)c[p].hl=v;else c[p].hr=v;return;}pushdown(p);int mid=l+r>>1;if(mid>=L)change(ls[p],l,mid,L,R,v,op);if(mid<R)change(rs[p],mid+1,r,L,R,v,op);pushup(p);}int query(int p,int l,int r,int w){if(l==r)return min({c[p].tagl,c[p].tagr,c[p].v});pushdown(p);int mid=l+r>>1;if(mid>=w)return query(ls[p],l,mid,w);return query(rs[p],mid+1,r,w);}int changer(int p,int l,int r,int w,int v){if(w>=r){c[p].tagr=min(c[p].tagr,v);return max(c[p].hl,v);}pushdown(p);int mid=l+r>>1;if(mid>=w)return changer(ls[p],l,mid,w,v);return changer(ls[p],l,mid,w,changer(rs[p],mid+1,r,w,v));}int changel(int p,int l,int r,int w,int v){if(w<=l){c[p].tagl=min(c[p].tagl,v);return max(c[p].hr,v);}pushdown(p);int mid=l+r>>1;if(w>mid)return changel(rs[p],mid+1,r,w,v);return changel(rs[p],mid+1,r,w,changel(ls[p],l,mid,w,v));}
}seg;
signed main(){n=read(),q=read();h[1]=h[n+1]=inf;for(int i=2;i<=n;i++)h[i]=read();n++;rt[0]=seg.build(1,n);for(int i=1,op,c,x,y;i<=q;i++){op=read(),c=read(),x=read();rt[i]=seg.New(rt[c]);if(op==0){y=read();int l=seg.queryl(rt[i],1,n,x,y),r=seg.queryr(rt[i],1,n,x+1,y)-1;seg.change(rt[i],1,n,l,r,y,0);}else if(op==1){seg.changel(rt[i],1,n,x,0);seg.changer(rt[i],1,n,x,0);}else if(op==2){y=read();seg.change(rt[i],1,n,x+1,x+1,y,1);seg.change(rt[i],1,n,x,x,y,2);}else printf("%d\n",seg.query(rt[i],1,n,x));}return 0;
}