初闻满座惊，OP 树科技迎来翻新！

Melo_qwq · 2026-02-02 11:27:08 · 休闲·娱乐

注：此科技由万人敬仰的学长 OPTIM（lelekue）和 PDQB 以及大帅哥耳朵龙联合创造，但是由于所有记载都在校内 OJ，过于可惜所以我搬了过来，增加了一些魔怔以及复杂度证明。

声明：OP 的原因是二人的首字母，与某游戏玩家并没有关系，虽然我也不知道两个学长玩不玩。

首先 OP 树是一个堆。

OP 树支持以均摊 O(\log n) 的复杂度插入元素、合并堆、删除堆顶以及 O(1) 查询堆顶。

显然 OP 树中的某个节点应该有左右儿子以及值。

仰之弥高，钻之弥坚。瞻之在前，忽焉在后。OP 树令人拍案叫绝，所以我们对每个节点额外维护一个字符变量 woc，其值为 O 或者 P。

根据“无知时诋毁\blacksquare\blacksquare”可知，woc 初始值应该为 P。

以下给出 OP 树的具体操作过程，以合并堆为例：

当我们合并两个堆，堆顶分别为 x 和 y（不妨令 x 为合并后的堆顶）时：

先考察当前节点 x，中华文化，博大精深，O 非常高贵，而古人以左为尊，所以如果 woc[x]='O'，我们将 y 与 x 的左儿子合并，否则与右儿子合并。
天道无欺，机会均之。一个节点高贵的 O 属性并不能一直保持下去，所以我们在合并后将点 x 的 OP 属性取反，可以保证 OP 树中元素地位平等。

这就是 OP 树的合并堆过程，其他操作则是本质相同的。

接下来考虑证明复杂度，显然只需要考虑合并的复杂度。

称呼一个节点 x 是⚪的当且仅当：

若 woc[x]='O'，那么要求 siz_{ls_x}>siz_{rs_x}，其中 siz 表示节点数。
否则反之。

考虑设计势能函数 \varphi_t 表示 t 次操作后⚪的节点的个数（假设一共是 n 次操作），则显然满足条件 \varphi_0=0 且 \forall i,\varphi_i\ge \varphi_0。

考虑每次合并操作，设（当前是第 i 次操作）以 x 和 y 为顶的堆中⚪和不⚪的节点我们分别经过了 h_x,l_x,h_y,l_y 个，那么显然实际开销 c_i=h_x+l_x+h_y+l_y。

考虑单次操作时，如果某个节点是⚪的，那么往他（或者他的子堆）里面合并另一个堆，他仍然是⚪的，操作后属性取反他一定不是⚪的。

即 h_x,h_y 所包含的这些节点本次操作后一定不是⚪的。

考虑最坏情况，l_x,l_y 中的所有节点都变成了⚪的，但是显然这样的节点不会超过 \log n 个（我们不妨认为节点数是 O(n) 的）。

所以这次操作的势能变化量 \Delta\varphi\le l_x+l_y-h_x-h_y。

所以此次的均摊开销 \hat{c}_i=c_i+\Delta\varphi\le2\times(l_x+l_y)\le 2\log n。

证毕。

尽管功能比较有限，但是确实是一种短小精悍且理解起来脑瘫瘫的科技。

可以轻松通过【模板】可并堆 1。

码长在我这种长度常数奇大无比的选手手下仍然只有 1.4kb，效率稳定处于 200ms 左右。

给出一份参考实现：

#include "bits/stdc++.h"
#define f(i ,m ,n ,x) for (int i = (m) ; i <= (n) ; i += (x))

const int N = 1e5 + 25 ;
int G ,e ,n ,s ,h ,i[N] ;

class OPTree {
private :
    int fa[N] ,rt[N] ,val[N] ,ls[N] ,rs[N] ; char woc[N] ; bool del[N] ;

    inline int Find (int x)
    <% return x == fa[x] ? x : fa[x] = Find (fa[x]) ;%>

    inline int PreMerge (int x ,int y) {
        if (!x || !y) return x | y ;
        if (val[x] > val[y] || (val[x] == val[y] && x > y)) std :: swap (x ,y) ;
        if (woc[x] == 'O') ls[x] = PreMerge (ls[x] ,y) ;
        else rs[x] = PreMerge (rs[x] ,y) ;
        woc[x] = woc[x] == 'O' ? 'P' : 'O' ;
        return x ;
    }
public :
    inline void Init (int i)
    <% return val[rt[i] = fa[i] = i] = ::i[i] ,woc[i] = 'P' ,void () ;%>

    inline void Merge (int x ,int y) {
        if (del[x] || del[y]) return ;
        if ((x = Find (x)) == (y = Find (y))) return ;
        return fa[y] = x ,rt[x] = PreMerge (rt[x] ,rt[y]) ,void () ;
    }

    inline int Delete (int x) {
        if (del[x]) return -1 ;
        int ans = val[rt[x = Find (x)]] ;
        del[rt[x]] = true ,rt[x] = PreMerge (ls[rt[x]] ,rs[rt[x]]) ;
        return ans ;
    }
} OP ;

int main (void) {
    std :: ios :: sync_with_stdio (false) ,
    std :: cin.tie (nullptr) ,std :: cout.tie (nullptr) ;

    std :: cin >> n >> s ;
    f (i ,1 ,n ,1) std :: cin >> ::i[i] ,OP.Init (i) ;
    while (s --> 0) {
        std :: cin >> G >> e ;
        if (G == 1) {
            std :: cin >> h ;
            OP.Merge (e ,h) ;
        } else std :: cout << OP.Delete (e) << '\n' ;
    }
    return 0 ;
}

再次叠甲：我们不玩原神。

哦，这个是不是叫斜堆来着。