题解：P11266 【模板】完全体·堆

Phartial · 2024-11-29 20:47:59 · 题解

什么年代了还在写左偏树 / pbds，不如来看看我们高贵的斜堆！！！

以下提到堆默认小根堆。

斜堆的结构与普通的可并堆相同，但它的 merge 操作惊人的简单：

• 对于两个斜堆 t_1,t_2，假设 t_1 的根节点权值小于 t_2 的根节点权值，那么我们先将 t_2 合并到 t_1 的右子树中，再交换 t_1 的左右子树。

有了 merge 操作后，其余几个操作也是简单的了：

• push、top：过于平凡；
• decrease-key：找到目标节点，断开它与父亲的边，然后直接修改它的权值，重新合并回原堆；
• erase：把要删的节点权值 decrease-key 成 -\infty，然后直接合并根的左右子树作为新堆。

好那这个这么厉害的东西时间复杂度为啥是对的呢？？？

定义重点为右子树大小大于左子树的节点，轻点为右子树大小不大于左子树的节点。

容易发现一次 merge 的时间复杂度与两个堆最右链长度之和等阶，考虑势能分析。定义一个堆的势能为其中重点的数量，由于一次 merge 后最右链上的重点显然都会变成轻点，即使轻点都变成重点，总的势能也只和两个堆最右链中轻点个数等阶。

而由于最右链上每遇到一个轻点子树大小都至少会减半，所以轻点个数最多只有 \Theta(\log n) 个，均摊后可知 merge 的时间复杂度为 \Theta(\log n)。

还有一个不够显然的事情是 decrease-key 中断掉与父亲的边可能导致一些轻点变成重点，但因为删掉的点必然在这一轻点的左子树中，所以这样的轻点个数仍然是 \Theta(\log n) 的，同样可以摊进去。

于是证完了，虽然时间复杂度几乎全是 \Theta(\log n) 但是跑起来飞快！！！

#include <limits>
#include <iostream>

using namespace std;

const int kN = 1e6 + 1;

struct E {
  int f, l, r, v;
} e[kN];
int n, q, r[kN];

int M(int x, int y) {
  if (!x || !y) {
    return x | y;
  }
  if (e[x].v > e[y].v) {
    swap(x, y);
  }
  e[e[x].r = M(e[x].r, y)].f = x, swap(e[x].l, e[x].r);
  return x;
}
void D(int &r, int x, int v) {
  int y = e[x].f;
  (y ? e[y].l == x ? e[y].l : e[y].r : r) = e[x].f = 0;
  e[x].v = v, r = M(r, x);
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> q;
  for (int i = 1; i <= n; ++i) {
    cin >> e[i].v;
    r[i] = i;
  }
  for (int o, x, y, z; q--; ) {
    cin >> o >> x;
    if (o == 0) {
      cin >> y;
      D(r[x], y, numeric_limits<int>::min());
      e[r[x] = M(e[r[x]].l, e[r[x]].r)].f = 0;
    } else if (o == 1) {
      cout << e[r[x]].v << '\n';
    } else if (o == 2) {
      cin >> y;
      e[r[x] = M(r[x], r[y])].f = 0;
    } else {
      cin >> y >> z;
      D(r[x], y, z);
    }
  }
  return 0;
}