一開始想傻了囧……不過很快就發現這其實是個超級大水題……
考慮斜堆中
最后插入的那個結點，容易發現：
（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;
}