左偏树【待施工】
2022/7/23 23:28:25
本文主要是介绍左偏树【待施工】,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
#include<bits/stdc++.h> using namespace std; const int N = 1e5 + 10; int fa[N],ls[N],rs[N],dist[N],val[N],id[N]; bool del[N]; int n,m,cnt; int get(int x) { if(x == fa[x])return x; return fa[x] = get(fa[x]); } struct leftist { int id,val; bool operator<(leftist x)const{return val == x.val?id<x.id:val < x.val;} }t[N]; int mer(int x,int y) { if(!x||!y)return x|y; if(t[y]<t[x])swap(x,y); rs[x] = mer(rs[x],y); if(dist[ls[x]] < dist[rs[x]])swap(ls[x],rs[x]); dist[x] = dist[rs[x]] + 1; return x; } int main() { cin >> n >> m; dist[0] = -1; for(int i = 1 ; i <= n ; i ++ ) { scanf("%d",&t[i].val); fa[i] = i; t[i].id = i; } for(int i = 1 ; i <= m ; i ++ ) { int x,y,op; scanf("%d%d",&op,&x); if(op == 1) { scanf("%d",&y); if(del[x]||del[y])continue; x = get(x),y = get(y); if(x != y)fa[x] = fa[y] = mer(x,y); } else { if(del[x]){puts("-1");continue;} x = get(x); printf("%d\n",t[x].val); del[x] = 1; fa[ls[x]] = fa[rs[x]] = fa[x] = mer(ls[x],rs[x]); ls[x] = rs[x] = dist[x] = 0; } } }
这篇关于左偏树【待施工】的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?
- 2024-05-09企业src漏洞挖掘-有意思的命令执行