一開始想傻了囧……不過很快就發(fā)現(xiàn)這其實是個超級大水題……
考慮斜堆中
最后插入的那個結(jié)點，容易發(fā)現(xiàn)：
（1）它一定是一個極左結(jié)點（就是從根往它的路上一直都是沿著左鏈走），因為插入的時候每次都是插入到左子樹中；
（2）它一定木有右子樹，因為插入的時候每次都是把原來的某棵子樹作為新結(jié)點的左子樹；
滿足（1）（2）的結(jié)點可能有多個，但緊接著可以發(fā)現(xiàn)，這個
斜堆中的每個結(jié)點如果木有左子結(jié)點，那么也木有右子結(jié)點（或者說，每個非葉結(jié)點都有左子樹），而在插入一個結(jié)點之前，其所有的祖先都被交換了左右子樹，所以，若新結(jié)點的祖先中有滿足（1）（2）的，且新結(jié)點不是葉結(jié)點，那么在新結(jié)點插入之前，這個滿足（1）（2）的祖先必然是只有右子樹而木有左子樹的，這與上面的那個性質(zhì)矛盾，所以，可以得出：
最后插入的那個結(jié)點一定是滿足（1）（2）的結(jié)點中，深度最小的那個（設(shè)為X），除非X的左子結(jié)點是葉結(jié)點，此時為了滿足字典序最小，應(yīng)該取X的左子結(jié)點為最后插入的。找到這個最后插入的結(jié)點以后，只需要把它刪掉，并把它的所有祖先交換左右子樹，就是插入該結(jié)點以前的狀態(tài)了。這樣可以找到字典序最小的插入順序。
———————————————————————————————————————————————————
但是，這個題的意義還不止于此，必須要搞清楚斜堆到底是什么，有什么應(yīng)用囧……
斜堆是可合并堆的一種實現(xiàn)形式，其更穩(wěn)定的實現(xiàn)是左偏樹（斜堆只能做到均攤logN，而左偏樹則可以嚴(yán)格做到每次操作O(logN)）。
斜堆最典型的特點，上面已經(jīng)說過了，如果一個結(jié)點沒有左子樹，那么它也一定沒有右子樹。這樣，大多數(shù)斜堆看上去是往左傾斜的（這也就是它的名字的由來……）。如果給每個結(jié)點加上一個
距離值dist[]，為該結(jié)點到它最近的沒有右子樹的子結(jié)點的距離，并且滿足任意結(jié)點的左子結(jié)點的距離值都不小于右子結(jié)點的距離值的話，就成了左偏樹囧……
可合并堆，顧名思義，它必須滿足兩個性質(zhì)：（1）是堆，也就是每個結(jié)點的關(guān)鍵字都不大于（小頂堆）/不小于（大頂堆）其兩個子結(jié)點的關(guān)鍵字；（2）它必須在O(logN)時間內(nèi)完成合并操作，即將兩個堆合并為一個，且合并成的堆仍滿足原來的性質(zhì)。
斜堆的合并操作有點像某些函數(shù)式數(shù)據(jù)結(jié)構(gòu)，但它并不會動用額外的空間。該合并操作使用遞歸實現(xiàn)，設(shè)兩個斜堆（小頂堆）的根結(jié)點為A、B，若A和B中的某一個為空，則返回另一個；若A和B均非空，則先將它們中關(guān)鍵字小的那個的右子樹與關(guān)鍵字大的那個的整棵樹合并，作為關(guān)鍵字小的那個的新的右子樹，然后，如果是左偏樹的話要更新dist，若dist不滿足“左不小于右”，還要交換左右子樹。
斜堆可以支持的操作有（指能在O(logN)時間內(nèi)完成的操作）：
（1）插入結(jié)點：（用合并實現(xiàn)）；
（2）刪除任意結(jié)點：（將待刪除結(jié)點的兩棵子樹合并，取代原來的位置，若是左偏樹的話還要往上更新dist直到dist不變?yōu)橹梗痴撐睦镉凶C明，每次刪除更新dist次數(shù)不會超過2logN）；
（3）合并兩個斜堆；
（4）找最小/大值；
（5）求以某個結(jié)點為根的子樹大小（維護(hù)sz即可）；
斜堆不能支持的操作有（指不能在O(logN)時間內(nèi)完成的操作）：
（1）查找任意結(jié)點。因此，若要刪除某個指定結(jié)點，則必須先用下標(biāo)等索引到它；
（2）找第K小（如果這個都能實現(xiàn)的話，斜堆就可以替代平衡樹了囧……還是可合并平衡樹……）；
（3）找某個結(jié)點所在樹的根結(jié)點（但是配合并查集+索引可以實現(xiàn)，詳見HDU1512）；
至于編程復(fù)雜度方面……非常非常好寫！基本上一個合并操作就夠了，<10行（斜堆的好寫程度僅次于并查集和普通堆）；
寫的之后有三個主要的易疵點：
（1）合并的時候別忘了更新一些東東，尤其別忘了返回根結(jié)點；
（2）（極易疵的！！）如果要刪除某個結(jié)點，必須把它的所有信息恢復(fù)到孤立結(jié)點的狀態(tài)，即斷開與原樹的一切聯(lián)系（pr、L、R全部置0），dist（如果是左偏樹）置0、sz置1；（3）下標(biāo)從1開始，0號結(jié)點作特殊用途（dist值為-1，sz值為0），如果某個結(jié)點的pr、L、R不存在則為0；
例題（由于想穩(wěn)定，本沙茶全都是用左偏樹寫的囧）：
【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，同時也可以考察數(shù)據(jù)結(jié)構(gòu)的綜合應(yīng)用能力。
#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;
}