@[intirain](/user/723993) 这个题不是修改任意数的，哥
by Hot_tear @ 2024-02-17 19:24:26
@[intirain](/user/723993) 你这个只是修改左偏树的根，哥
by Hot_tear @ 2024-02-17 19:25:15
@[Hot_tear](/user/737112) 不好意思没看清 让我想想（）
by __ryp__ @ 2024-02-17 19:25:56
@[Hot_tear](/user/737112) [OI Wiki](https://oi-wiki.org/ds/leftist-tree/#%E5%88%A0%E9%99%A4%E4%BB%BB%E6%84%8F%E8%8A%82%E7%82%B9) 或许能告诉你
by __ryp__ @ 2024-02-17 19:26:41
@[intirain](/user/723993) 没事哒/QwQ
by Hot_tear @ 2024-02-17 19:27:00
@[intirain](/user/723993) 它只是给了思想，没有给出具体代码，我就是对着si'xian跳了一下午/yun
by Hot_tear @ 2024-02-17 19:27:32
@[Hot_tear](/user/737112) 思想
by Hot_tear @ 2024-02-17 19:27:43
@[Hot_tear](/user/737112) 它这个和平衡树的删除有点像，但是简单的多，就是将待删除节点的左右两个孩子直接合并。
有个坑就是你必须每层 `pushup`，这个玩意儿我调红黑树的时候卡了我两天
另外看看你代码？
by __ryp__ @ 2024-02-17 19:30:06
@[intirain](/user/723993) 诺
```cpp
#include<bits/stdc++.h>
#define ll long long
#define F(i,a,b) for(ll i=a;i<=b;i++)
#define R(i,a,b) for(ll i=a;i>=b;i--)
#define sc(a) scanf("%lld",&a)
#define ps(a) printf("%lld ",a)
#define pn(a) printf("%lld\n",a)
using namespace std;
const ll N=3e6+7;
ll n,m,fa[N],dist[N],l[N],r[N],opt,x,y;
struct edge{
ll val,id;
bool operator<(const edge& a)const{
return val==a.val?id<a.id:val<a.val;
}
}v[N];
bool vis[N];
inline ll find(ll x){
return x==fa[x]?fa[x]:fa[x]=find(fa[x]);
}
inline ll merge(ll x,ll y){
if(!x||!y) return x|y;
if(v[y]<v[x]) swap(x,y);
r[x]=merge(r[x],y);
if(dist[r[x]]>dist[l[x]]) swap(l[x],r[x]);
dist[x]=dist[r[x]]+1;
return x;
}
inline void Delete(ll x){
ll q=fa[x];
ll p=merge(l[x],r[x]);
fa[l[x]]=fa[r[x]]=fa[x]=p;
l[x]=r[x]=0,dist[x]=-1;
if(q&&l[q]==x) l[q]=p;
if(q&&r[q]==x) r[q]=p;
while(q){
if(dist[l[q]]<dist[r[q]]) swap(l[q],r[q]);
if(dist[q]==dist[r[q]]+1) return ;
dist[q]=dist[r[q]]+1;
q=fa[q];
}
}
int main(){
dist[0]=-1;
sc(n),sc(m);
F(i,1,n) sc(v[i].val),v[i].id=i,fa[i]=i;
F(i,1,m){
sc(opt),sc(x);
if(opt==1){
sc(y);
if(vis[x]||vis[y]||find(x)==find(y)) continue;
x=find(x),y=find(y);
fa[x]=fa[y]=merge(x,y);
}
else{
if(vis[x]){
puts("-1");
continue;
}
x=find(x);
pn(v[x].val);
Delete(x);
vis[x]=true;
}
}
return 0;
}
```
by Hot_tear @ 2024-02-17 19:33:34