Hdu传送门 左偏树模板题，细节一定要注意
#include<cstdio>#include<algorithm>#include<cstring>#define ms(i,j) memset(i,j,sizeof i);using namespace std;const int MAXN = 100000 + 5;struct node{ int l, r;//左偏树左、右孩子编号 int dis, key;//左偏树距离，键值 int f;//并查集father }lt[MAXN];int n;int m;int find(int x) //并查集find { return (x==lt[x].f) ? (x) : (lt[x].f = find(lt[x].f)); }void build(int rt, int v)//使rt初始化为v值 { lt[rt].l = lt[rt].r = lt[rt].dis = 0; lt[rt].key = v; lt[rt].f = rt; if (rt==0) lt[rt].dis = -1;}int merge(int rtA, int rtB)//合并两棵树 { if (rtA==0) return rtB; if (rtB==0) return rtA; if (lt[rtA].key<lt[rtB].key) swap(rtA, rtB);//大值左偏树要满足key(x)<key(parents[x]) lt[rtA].r = merge(lt[rtA].r, rtB);//A的右子树和B合并 int &l = lt[rtA].l, &r = lt[rtA].r;//利用引用减少代码量，更加清晰 lt[l].f = lt[r].f = rtA; //更新并查集 if (lt[l].dis<lt[r].dis) swap(l, r);//需要满足左偏性质dis(lc)>=dis(rc) if (r==0) lt[rtA].dis = 0; else lt[rtA].dis = lt[r].dis+1;//算距离 return rtA;}int del(int rt)//删除rt节点 { int l = lt[rt].l; int r = lt[rt].r; lt[l].f = l; lt[r].f = r; lt[rt].l = lt[rt].r = lt[rt].dis = 0; return merge(l, r);}int main(){ while (scanf("%d", &n)==1) { for (int i=1;i<=n;i++) { int x; scanf("%d", &x); build(i, x); } build(0, 0); scanf("%d", &m); for (int i=1;i<=m;i++) { int x,y; scanf("%d%d", &x, &y); int x1 = find(x); int x2 = find(y);//找最强壮的 if (x1==x2) {PRintf("-1/n");continue;} lt[x1].key>>=1; lt[x2].key>>=1;//之后插入的值 int left = del(x1), right = del(x2); left = merge(left, x1), right = merge(right, x2); left = merge(left, right); printf("%d/n", lt[left].key); } } fclose(stdin);fclose(stdout); return 0;}新闻热点
疑难解答
