本题的 $n$ 特别大,如果直接开那么大的空间,想必会直接超时。所以我们可以先把所有“用户”合并成一个点,需要访问到哪个就进行分裂。这样的话 $m$ 次操作每次都只会分裂一次,时间复杂度就能保证在 $O(m\log m)$ ,空间也不会炸。

另外本题只有提到最前面和提到最后面两种操作,使用平衡树的必要不大,用动态开点线段树就好了。

p.s. 感觉 Leafy Tree 和这个好像啊 (=’w’​=)

前言

和 Splay 一样,非旋 Treap (又名 fhq-treap)也是平衡树的一种。由于其不需要进行旋转操作,故可利用其进行可持久化。

写一颗非旋 Treap,我们只需要合并、分离操作,其他的只要有颗脑子就会了啦!

定义

我们定义类FhqTreap为非旋 Treap 主体,结构体node为其节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class FhqTheap {

private:

struct node {
int val, rnd; // val => 该点存储的值,rnd => 该点键值,随机产生
int siz, ch[2]; // siz => 该点包括其子树的节点大小,ch[2] => 指向左/右儿子
} e[maxn];
int tot, root; // tot => 节点总数,root => 根节点
int x, y, z; // 操作过程中的临时变量

// Your Code Goes Here...

public:

// Your Code Goes Here...

} s;

踏上平衡树征程的第一步…

前言

Splay 是一种简单且功能丰富的平衡树结构,其算法核心 Splay 操作能维持其均摊复杂度维持在 $O(logn)$ 。

定义

我们将整棵 Splay 定义在结构体中。

并定义结构体node来表示 Splay 的每一个节点。

宏定义e[0].ch[1]为根节点, $1e9 + 10$ 为INF,并在结构体尾取消定义。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct Splay {
#define root (e[0].ch[1])
#define inf (1e9+10)
struct node {
int val; // 当前节点存储的值
int cnt; // 当前节点存储的值出现的次数
int siz; // 当前节点包括其左右子树中包含的数的个数(不是节点数!)
int father; // 当前节点的父亲节点
int ch[2]; // 当前节点的孩子节点,ch[0]表示左孩子,ch[1]表示右孩子
}
// your code goes here...
#undef root
#undef inf
}

思路

之前我们讲到了用 Splay 写普通平衡树,这次我们将用 Splay 来完成区间操作。

之前的 Splay 是按照权值排序,而这里的 Splay 则是要按照编号排序。

不难想到,整棵树的编号第 k 大点即数列中的第 k 个,整棵树的中序遍历即被维护的数列。


假设我们要翻转区间[l, r],那么我们先把l - 1旋转到根节点,再把r + 1旋转到根节点的右孩子。那么r + 1的左子树即区间[l, r]。翻转该区间只需要把该区间内的每个节点的左右子树交换即可。

参考线段树的 lazytag,我们也使用一个类似于懒标记的方法,保证复杂度为O(log n)

1.png

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×