还记得当年坐在OZY大佬旁边被D的日子。。才发现现在妙已经变成权限题做不了（怕是要被DS）只能补补左偏树聊以自慰了。
这个东西呢其实也是堆的一种（也叫左偏堆），可以理解为维护大(小)根堆的，堆顶就是最大(小)值用d表示，然后l，r是左右孩子节点，c是管理人数。至于为什么叫做左偏树呢，是因为他一个奇怪的定义：左边的子树的节点数一定大于右边的子树的节点数，这样有什么好处呢？显然，我们如果插入节点从左往右，那就可以保证树的平衡。
其实这样看来，这个东西挺普通的，只是方便求最大(小)值，或者再拓展一下，管理多个集合，但是，它有一个关键的操作，就是Merge——合并！他可以支持两个左偏树的合并，具体怎么做呢？跟插入一个点是一样的，在右边插入，然后通过交换左右孩子，继续保持左偏性质，所以这个有一个限制——左右孩子可以交换，就是说不像伸展树类似的，左大右小什么的。
bzoj1455（现在也变成权限题了）时光荏再，物是人非啊。
#include<cstdio> #include<iostream> #include<cstring> using namespace std; struct heap { int l,r,c,d; heap() { l=0;r=0;c=0; } }h[1100000]; int Merge(int x,int y) { if(x==0||y==0)return x+y; if(h[x].d>h[y].d)swap(x,y);//维护小根堆 h[x].r=Merge(h[x].r,y);//让他到右边合并，令树平衡 if(h[h[x].l].c<h[h[x].r].c)swap(h[x].l,h[x].r);//保持左偏 h[x].c=h[h[x].r].c+1;//维护 return x; } int fa[1100000]; int findfa(int x)//用并查集来维护每一个团 { if(fa[x]==x)return x; fa[x]=findfa(fa[x]);return fa[x]; } bool v[1100000];//人有没有被杀 char ss[5]; int main() { int n,m,x,y; scanf("%d",&n); for(int i=1;i<=n;i++) { fa[i]=i; scanf("%d",&h[i].d); } memset(v,false,sizeof(v)); scanf("%d",&m); while(m--) { scanf("%s",ss+1); if(ss[1]=='M') { scanf("%d%d",&x,&y); if(v[x]==true||v[y]==true)continue; int fx=findfa(x),fy=findfa(y); if(fx==fy)continue;//是否在一个团里面 fa[fx]=fa[fy]=Merge(fx,fy);//合并两个堆，维护并查集，祖先是值最小的人 } else { scanf("%d",&x); if(v[x]==true){printf("0 ");continue;} int k=findfa(x);v[k]=true;//杀人 printf("%d ",h[k].d); fa[k]=Merge(h[k].l,h[k].r);//祖先是新的值最小的人 fa[fa[k]]=fa[k]; } } return 0; }