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

注：此科技由万人敬仰的学长 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，效率稳定处于

200

ms 左右。

给出一份参考实现：

CPP

#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 ;
}

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

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

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

文章操作

相关推荐

评论

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