为了反驳隔壁很对劲的太刀流，并不对劲的片手流将与之针锋相对。
很对劲的斜堆、左偏树简明教程->
它们是可并堆的两种实现方式。
（假装二叉堆只包括小根堆。）
二叉堆该如何合并？先想一种暴力的。
现在有根的键值较小的二叉堆A，键值较大的二叉堆B。
在合并后，A的根肯定还是根。若A的左、右子树都不为空的话，则可以随便选一个，再将这个堆与B合并。
递归地重复这个过程，直到左、右子树中有一方为空，直接接过去就行了。
然而这样时间复杂度并不会得到保障，因为每次“随便选”的那一个可能更深。这样时间复杂度就玄学了。
斜堆则是在暴力的基础上有一些修改。每次必选右（或左）子树合并，然后交换左右子树。这样下次就轮到这次没能合并的子树与之合并了。
这听上去和暴力区别不大，还有那么一些些的扯。但是类似于splay，它的时间复杂度均摊却是O(log n)的。至于证明，类似于splay，并不对劲的人并不知道，就感性理解吧。
加点操作相当于与一个只有一个节点的斜堆合并。
删除相当于去掉堆顶元素，再将它的左、右子树合并。
可以去洛谷p3377测评，斜堆好像也能过。
#include<iostream> #include<iomanip> #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<algorithm> #define maxn 100010 using namespace std; int read() { int f=1,x=0;char ch=getchar(); while(isdigit(ch)==0 && ch!='-')ch=getchar(); if(ch=='-')f=-1,ch=getchar(); while(isdigit(ch))x=x*10+ch-'0',ch=getchar(); return x*f; } void write(int x) { int ff=0;char ch[15]; if(x<0) { x=-x; putchar('-'); } while(x)ch[++ff]=(x%10)+'0',x/=10; if(ff==0)putchar('0'); while(ff)putchar(ch[ff--]); putchar(' '); } struct node { int key,ls,rs,dis; }xx[maxn]; int fa[maxn],n,q; int x,y,l,r,tx,ty; bool cmp(int _1,int _2)//Smaller. { return xx[_1].key==xx[_2].key?_1<_2:xx[_1].key<xx[_2].key; } int f(int x){return fa[x]<0?x:f(fa[x]);} int merge(int A,int B) { if(!A || !B)return A+B; if(!cmp(A,B))swap(A,B); xx[A].rs=merge(xx[A].rs,B); fa[xx[A].rs]=A; swap(xx[A].ls,xx[A].rs); return A; } void getit() { x=read(),y=read(); if(xx[x].key<0 || xx[y].key<0)return; tx=f(x),ty=f(y); if(tx==ty)return; merge(tx,ty); } void delmin(int u) { l=xx[u].ls,r=xx[u].rs; xx[u].key=fa[l]=fa[r]=-1; merge(l,r); } void ask() { // printfa(); x=read(); if(xx[x].key==-1){write(-1);return;} tx=f(x); write(xx[tx].key); delmin(tx); // printfa(); } void work() { n=read(),q=read(); xx[0].dis=-1; memset(fa,-1,sizeof(fa)); for(int i=1;i<=n;i++) xx[i].key=read(); int f; while(q--) { f=read(); if(f==1) getit(); else ask(); } } int main() { work(); return 0; } /* 5 5 1 5 4 2 3 1 1 5 1 2 5 2 2 1 4 2 2 2 */
好像写得比简明教程还简明呢。