一开始想傻了囧……不过很快就发现这其实是个超级大水题……
考虑斜堆中
最后插入的那个结点，容易发现：
（1）它一定是一个极左结点（就是从根往它的路上一直都是沿着左链走），因为插入的时候每次都是插入到左子树中；
（2）它一定木有右子树，因为插入的时候每次都是把原来的某棵子树作为新结点的左子树；
满足（1）（2）的结点可能有多个，但紧接着可以发现，这个
斜堆中的每个结点如果木有左子结点，那么也木有右子结点（或者说，每个非叶结点都有左子树），而在插入一个结点之前，其所有的祖先都被交换了左右子树，所以，若新结点的祖先中有满足（1）（2）的，且新结点不是叶结点，那么在新结点插入之前，这个满足（1）（2）的祖先必然是只有右子树而木有左子树的，这与上面的那个性质矛盾，所以，可以得出：
最后插入的那个结点一定是满足（1）（2）的结点中，深度最小的那个（设为X），除非X的左子结点是叶结点，此时为了满足字典序最小，应该取X的左子结点为最后插入的。找到这个最后插入的结点以后，只需要把它删掉，并把它的所有祖先交换左右子树，就是插入该结点以前的状态了。这样可以找到字典序最小的插入顺序。
———————————————————————————————————————————————————
但是，这个题的意义还不止于此，必须要搞清楚斜堆到底是什么，有什么应用囧……
斜堆是可合并堆的一种实现形式，其更稳定的实现是左偏树（斜堆只能做到均摊logN，而左偏树则可以严格做到每次操作O(logN)）。
斜堆最典型的特点，上面已经说过了，如果一个结点没有左子树，那么它也一定没有右子树。这样，大多数斜堆看上去是往左倾斜的（这也就是它的名字的由来……）。如果给每个结点加上一个
距离值dist[]，为该结点到它最近的没有右子树的子结点的距离，并且满足任意结点的左子结点的距离值都不小于右子结点的距离值的话，就成了左偏树囧……
可合并堆，顾名思义，它必须满足两个性质：（1）是堆，也就是每个结点的关键字都不大于（小顶堆）/不小于（大顶堆）其两个子结点的关键字；（2）它必须在O(logN)时间内完成合并操作，即将两个堆合并为一个，且合并成的堆仍满足原来的性质。
斜堆的合并操作有点像某些函数式数据结构，但它并不会动用额外的空间。该合并操作使用递归实现，设两个斜堆（小顶堆）的根结点为A、B，若A和B中的某一个为空，则返回另一个；若A和B均非空，则先将它们中关键字小的那个的右子树与关键字大的那个的整棵树合并，作为关键字小的那个的新的右子树，然后，如果是左偏树的话要更新dist，若dist不满足“左不小于右”，还要交换左右子树。
斜堆可以支持的操作有（指能在O(logN)时间内完成的操作）：
（1）插入结点：（用合并实现）；
（2）删除任意结点：（将待删除结点的两棵子树合并，取代原来的位置，若是左偏树的话还要往上更新dist直到dist不变为止，某论文里有证明，每次删除更新dist次数不会超过2logN）；
（3）合并两个斜堆；
（4）找最小/大值；
（5）求以某个结点为根的子树大小（维护sz即可）；
斜堆不能支持的操作有（指不能在O(logN)时间内完成的操作）：
（1）查找任意结点。因此，若要删除某个指定结点，则必须先用下标等索引到它；
（2）找第K小（如果这个都能实现的话，斜堆就可以替代平衡树了囧……还是可合并平衡树……）；
（3）找某个结点所在树的根结点（但是配合并查集+索引可以实现，详见HDU1512）；
至于编程复杂度方面……非常非常好写！基本上一个合并操作就够了，<10行（斜堆的好写程度仅次于并查集和普通堆）；
写的之后有三个主要的易疵点：
（1）合并的时候别忘了更新一些东东，尤其别忘了返回根结点；
（2）（极易疵的！！）如果要删除某个结点，必须把它的所有信息恢复到孤立结点的状态，即断开与原树的一切联系（pr、L、R全部置0），dist（如果是左偏树）置0、sz置1；（3）下标从1开始，0号结点作特殊用途（dist值为-1，sz值为0），如果某个结点的pr、L、R不存在则为0；
例题（由于想稳定，本沙茶全都是用左偏树写的囧）：
【1】
HDU1512基本操作题，配合并查集+索引找根即可；
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
#define rre1(i, n) for (int i=n; i>0; i--)
#define rre2(i, r, l) for (int i=r-1; i>=l; i--)
#define rre3(i, r, l) for (int i=r; i>=l; i--)
#define ll long long
const int MAXN = 100010, INF = ~0U >> 2;
int n, u[MAXN], rt[MAXN], V[MAXN], dist[MAXN], pr[MAXN], L[MAXN], R[MAXN], res;
int UFS_find(int x)
{
int tmp = x, r = x; while (u[r] >= 0) r = u[r]; while (x != r) {tmp = u[x]; u[x] = r; x = tmp;} return r;
}
void UFS_union(int s1, int s2, int rt0)
{
if (u[s1] >= u[s2]) {u[s1] = s2; u[s2]--; rt[s2] = rt0;} else {u[s2] = s1; u[s1]--; rt[s1] = rt0;}
}
int heap_union(int s1, int s2)
{
if (!s1) return s2; else if (!s2) return s1; else if (V[s1] >= V[s2]) {
int z = heap_union(R[s1], s2);
R[s1] = z; pr[z] = s1; if (dist[L[s1]] < dist[z]) {int tmp = L[s1]; L[s1] = R[s1]; R[s1] = tmp;}
dist[s1] = dist[R[s1]] + 1; return s1;
} else {
int z = heap_union(s1, R[s2]);
R[s2] = z; pr[z] = s2; if (dist[L[s2]] < dist[z]) {int tmp = L[s2]; L[s2] = R[s2]; R[s2] = tmp;}
dist[s2] = dist[R[s2]] + 1; return s2;
}
}
void prepare()
{
dist[0] = -1; re1(i, n) {u[i] = -1; rt[i] = i; dist[i] = pr[i] = L[i] = R[i] = 0;}
}
void solve(int x, int y)
{
int s1 = UFS_find(x), s2 = UFS_find(y); if (s1 == s2) {res = -1; return;}
int rt1 = rt[s1], rt2 = rt[s2];
int z1 = heap_union(L[rt1], R[rt1]); L[rt1] = R[rt1] = pr[z1] = 0;
V[rt1] /= 2; z1 = heap_union(rt1, z1); pr[z1] = 0;
int z2 = heap_union(L[rt2], R[rt2]); L[rt2] = R[rt2] = pr[z2] = 0;
V[rt2] /= 2; z2 = heap_union(rt2, z2); pr[z2] = 0;
int z = heap_union(z1, z2); pr[z] = 0;
UFS_union(s1, s2, z);
res = V[z];
}
int main()
{
int m, x0, y0;
while (scanf("%d", &n) != EOF) {
re1(i, n) scanf("%d", &V[i]); prepare();
scanf("%d", &m);
re(i, m) {
scanf("%d%d", &x0, &y0);
solve(x0, y0);
printf("%d\n", res);
}
}
return 0;
}
【2】
HDU3031综合操作题，需要sz，同时也可以考察数据结构的综合应用能力。
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
#define rre1(i, n) for (int i=n; i>0; i--)
#define rre2(i, r, l) for (int i=r-1; i>=l; i--)
#define rre3(i, r, l) for (int i=r; i>=l; i--)
#define ll long long
const int MAXN = 1000010, MAXM = 101, MAXLEN_M = 10010, INF = ~0U >> 2;
int n, m, len[MAXM], V0[MAXM][MAXLEN_M], root[2];
int V[MAXN], dist[MAXN], pr[MAXN], L[MAXN], R[MAXN], sz[MAXN];
bool FS;
void upd(int x)
{
sz[x] = sz[L[x]] + sz[R[x]] + 1;
}
int heap_union(int s1, int s2)
{
if (!s1) return s2; else if (!s2) return s1; else if (V[s1] >= V[s2]) {
int s0 = heap_union(R[s1], s2);
pr[s0] = s1; R[s1] = s0; if (dist[L[s1]] < dist[s0]) {int tmp = L[s1]; L[s1] = R[s1]; R[s1] = tmp;} dist[s1] = dist[R[s1]] + 1; upd(s1);
return s1;
} else {
int s0 = heap_union(s1, R[s2]);
pr[s0] = s2; R[s2] = s0; if (dist[L[s2]] < dist[s0]) {int tmp = L[s2]; L[s2] = R[s2]; R[s2] = tmp;} dist[s2] = dist[R[s2]] + 1; upd(s2);
return s2;
}
}
void opr_T(int x)
{
sort(V0[x], V0[x] + len[x]); int root0 = n + 1;
rre(i, len[x]) {
n++; if (i == len[x] - 1) pr[n] = 0; else pr[n] = n - 1; if (i) L[n] = n + 1; else L[n] = 0; R[n] = dist[n] = 0; V[n] = V0[x][i]; sz[n] = i + 1;
}
root[FS] = heap_union(root[FS], root0);
}
void opr_A(int x)
{
V[root[FS]] += x;
}
void opr_E(int x)
{
int root0 = root[FS], z0; pr[z0 = heap_union(L[root0], R[root0])] = 0; L[root0] = R[root0] = dist[root0] = 0; sz[root0] = 1; V[root0] = x;
root[FS] = heap_union(z0, root0);
}
void opr_L()
{
int root0 = root[FS], z0; pr[z0 = heap_union(L[root0], R[root0])] = 0; L[root0] = R[root0] = dist[root0] = 0; sz[root0] = 1;
}
void opr_C()
{
int root0 = root[0], root1 = root[1];
if (V[root0] > V[root1]) {
root[0] = heap_union(root0, root1); root[1] = 0;
} else if (V[root0] < V[root1]) {
root[1] = heap_union(root0, root1); root[0] = 0;
}
}
int main()
{
int tests, sc0 = 0, sc1 = 0, P, tmp; char ssss[10];
scanf("%d", &tests);
re(testno, tests) {
scanf("%d%d", &P, &m);
re(i, m) scanf("%d", &len[i]);
re(i, m) re(j, len[i]) scanf("%d", &V0[i][j]); n = root[0] = root[1] = 0; dist[0] = -1; sz[0] = 0; FS = 0;
re(i, P) {
scanf("%s", ssss);
if (ssss[0] == 'T') {scanf("%d", &tmp); opr_T(--tmp);}
else if (ssss[0] == 'A') {scanf("%d", &tmp); opr_A(tmp);}
else if (ssss[0] == 'E') {scanf("%d", &tmp); opr_E(tmp);}
else if (ssss[0] == 'L') opr_L(); else opr_C();
FS = !FS;
}
printf("%d:%d\n", sz[root[0]], sz[root[1]]);
if (sz[root[0]] >= sz[root[1]]) sc0++; else sc1++;
}
if (sc0 > sc1) puts("Hahaha
I win!!"); else puts("I will be back!!");
return 0;
}