水池
有一个长条形的水池，可以划分成 (n) 格。其中第 (i) 格和 (i+1) 格之间相邻，由一块高度为 (h_i) 的可调节挡板隔开。第 (1) 格左侧和第 (n) 格右侧是无限高的池壁。初始时水池中没有水。现在进行 (q) 次操作，操作有以下四种：
-
0 i x h在第 (x) 格灌水直到该格的水面高度不低于 (h)（若当前水面高度已经达到 (h) 则无事发生）； -
1 i x打开第 (x) 格底部的排水口直到该格的水流干，再关闭排水口； -
2 i x h将第 (x) 格右侧的挡板高度增加到 (h)（不改变现有水面，保证挡板高度不会下降）； -
3 i x查询第 (x) 格的水面高度。
其中，(i) 表示这次操作是基于第 (i) 次操作之后的情况，(i=0) 表示基于初始状态。也就是说，这个问题要求对操作可持久化。
对于所有数据，(1le n,qle 2 imes 10^5, 0le h_ile 10^9)。
题解
https://blog.csdn.net/EI_Captain/article/details/107179167
这个题的限制并不强，感觉可持久化好像不是啥特别的限制。
首先考虑往上灌水的操作，这个主要是找出左右第一个(ge h)的隔板，在线段树上维护整段的隔板最高高度就可以做到。
抽水的话其实还是相当于要先扣出往两边走出的(le h)隔板部分的单调栈，因此抽水我们考虑给 tag 增加一种可能性，就是从整段从一边抽空，但是已知这段边界之外有一个长为(x)的隔板。注意在提升一块隔板的时候这个 tag 也是要下推的。整个问题没有什么均摊的情况，所以直接可持久化就好了。离线好像也没想到什么避免空间(Theta(n + mlog n))的办法。
CO int N=2e5+10,inf=1e9;
int h[N];
CO int NO=0,FI=1,LF=2,RF=3;
int root[N],tot;
struct node {int val,tag,baf[2],ch[2];} P[N*200];
#define mid ((l+r)>>1)
IN void push_up(int x){
for(int i=0;i<2;++i) P[x].baf[i]=max(P[P[x].ch[0]].baf[i],P[P[x].ch[1]].baf[i]);
}
int build(int l,int r){
int x=++tot;
if(l==r){
P[x].baf[0]=h[l-1],P[x].baf[1]=h[l];
return x;
}
P[x].ch[0]=build(l,mid);
P[x].ch[1]=build(mid+1,r);
push_up(x);
return x;
}
void push_down(int x){
if(P[x].tag==NO) return;
for(int i=0;i<2;++i) P[++tot]=P[P[x].ch[i]],P[x].ch[i]=tot;
if(P[x].tag==FI){
for(int i=0;i<2;++i) P[P[x].ch[i]].val=P[x].val,P[P[x].ch[i]].tag=FI;
P[x].tag=NO;
return;
}
int dir=P[x].tag-LF,cur=P[x].val,p=!dir;
do{
P[P[x].ch[p]].val=cur,P[P[x].ch[p]].tag=P[x].tag;
cur=max(cur,P[P[x].ch[p]].baf[dir]),p=!p;
}while(p!=!dir);
P[x].tag=NO;
}
template<bool dir>
int chkmax(int x,int l,int r,int p,int v){
P[++tot]=P[x],x=tot;
if(l==r){
P[x].baf[dir]=v;
return x;
}
push_down(x);
if(p<=mid) P[x].ch[0]=chkmax<dir>(P[x].ch[0],l,mid,p,v);
else P[x].ch[1]=chkmax<dir>(P[x].ch[1],mid+1,r,p,v);
push_up(x);
return x;
}
template<bool dir>
int bound(int x,int l,int r,int v){
if(P[x].baf[dir]<v) return -1;
if(l==r) return l;
int ans=bound<dir>(P[x].ch[!dir],!dir?(mid+1):l,!dir?r:mid,v);
if(ans==-1) ans=bound<dir>(P[x].ch[dir],dir?(mid+1):l,dir?r:mid,v);
return ans;
}
template<bool dir>
int bound(int x,int l,int r,int p,int v){
if(P[x].baf[dir]<v) return -1;
if(l==r) return l;
int ans=-1;
if(p<=mid){
ans=bound<dir>(P[x].ch[0],l,mid,p,v);
if(ans==-1 and dir==1) ans=bound<dir>(P[x].ch[1],mid+1,r,v);
}
else{
ans=bound<dir>(P[x].ch[1],mid+1,r,p,v);
if(ans==-1 and dir==0) ans=bound<dir>(P[x].ch[0],l,mid,v);
}
return ans;
}
int fill(int x,int l,int r,int ql,int qr,int v){
P[++tot]=P[x],x=tot;
if(ql<=l and r<=qr){
P[x].val=v,P[x].tag=FI;
return x;
}
push_down(x);
if(ql<=mid) P[x].ch[0]=fill(P[x].ch[0],l,mid,ql,qr,v);
if(qr>mid) P[x].ch[1]=fill(P[x].ch[1],mid+1,r,ql,qr,v);
return x;
}
int ans;
int query(int x,int l,int r,int p){
P[++tot]=P[x],x=tot;
if(l==r){
ans=P[x].val;
return x;
}
push_down(x);
if(p<=mid) P[x].ch[0]=query(P[x].ch[0],l,mid,p);
else P[x].ch[1]=query(P[x].ch[1],mid+1,r,p);
return x;
}
template<bool dir>
int pour(int x,int l,int r,int ql,int qr){
P[++tot]=P[x],x=tot;
if(ql<=l and r<=qr){
P[x].val=ans,P[x].tag=LF+dir;
ans=max(ans,P[x].baf[dir]);
return x;
}
push_down(x);
if(qr<=mid) P[x].ch[0]=pour<dir>(P[x].ch[0],l,mid,ql,qr);
else if(ql>mid) P[x].ch[1]=pour<dir>(P[x].ch[1],mid+1,r,ql,qr);
else if(dir){
P[x].ch[0]=pour<dir>(P[x].ch[0],l,mid,ql,qr);
P[x].ch[1]=pour<dir>(P[x].ch[1],mid+1,r,ql,qr);
}
else{
P[x].ch[1]=pour<dir>(P[x].ch[1],mid+1,r,ql,qr);
P[x].ch[0]=pour<dir>(P[x].ch[0],l,mid,ql,qr);
}
return x;
}
#undef mid
int main(){
int n=read<int>(),m=read<int>();
for(int i=1;i<n;++i) read(h[i]);
h[0]=h[n]=inf;
root[0]=build(1,n);
for(int i=1;i<=m;++i){
int opt=read<int>();
root[i]=root[read<int>()];
if(opt==0){
int p=read<int>(),h=read<int>();
root[i]=query(root[i],1,n,p);
if(ans<h){
int l=bound<0>(root[i],1,n,p,h);
int r=bound<1>(root[i],1,n,p,h);
root[i]=fill(root[i],1,n,l,r,h);
}
}
else if(opt==1){
int p=read<int>();
root[i]=query(root[i],1,n,p);
int l=bound<0>(root[i],1,n,p,ans);
int r=bound<1>(root[i],1,n,p,ans);
ans=0;
root[i]=pour<0>(root[i],1,n,l,p);
ans=0;
root[i]=pour<1>(root[i],1,n,p,r);
}
else if(opt==2){
int p=read<int>(),h=read<int>();
root[i]=chkmax<1>(root[i],1,n,p,h);
root[i]=chkmax<0>(root[i],1,n,p+1,h);
}
else{
int p=read<int>();
root[i]=query(root[i],1,n,p);
printf("%d
",ans);
}
}
return 0;
}