数据结构

Ztemily 发布于

平衡树

我们需要维护一种数据结构，支持以下操作：插入值，删除值，查询数在集合中的排名，查询排名为 kk 的数，求某个数的前驱与后继。

我们可以用二叉搜索树维护，但是可以被卡成 O(n)O(n) ，那么我们要用到另外一种数据结构，即平衡树来维护这些操作。

平衡树种类较多，这里仅介绍其中的Splay、Treap、FHQ Treap。

Splay

平衡树是基于BST也就是二叉搜索树的结构来进行维护的，它有一些性质。

左儿子 << 根 << 右儿子，这里的小于号可以自定义。且中序遍历可以得到一个有序序列。

我们在正常情况下显然可以用BST的特性去跳左右儿子就可以找到目标节点，但是在链数据下会从 O(log)O(log) 复杂度卡成 o(n)o(n)。

那么，Splay就是通过其独特的旋转操作，用旋学来稳定玄学的 O(log(n))O(log(n)) 复杂度。

关于每个节点我们需要存储的信息有这些：父节点与子节点编号，权值，权值出现次数与此节点所在子树的大小。

那么我们可以写出维护其基本性质的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
const int Maxn = 1e5 + 10;
#define ls(x) son[x][0]
#define rs(x) son[x][1]

int fa[Maxn], son[Maxn][2];
int val[Maxn], cnt[Maxn];
int siz[Maxn];

inline void clear(int x)
{
    return ls(x) = rs(x) = f[x] = siz[x] = cnt[x] = val[x] = 0, void();
} //删除节点

inline bool get(int x)
{
    return (rs(f[x]) == x);
} //判断节点是左儿子还是右儿子

inline void up(int x)
{
    if (x)
    {
        siz[x] = cnt[x];
        ls(x) ? siz[x] += siz[ls(x)] : siz[x] = siz[x];
        rs(x) ? siz[x] += siz[rs(x)] : siz[x] = siz[x];
    }

    return;
} //上传

那么下一步就是Splay的精髓所在——旋转。

我们根据不同的情况去调整，直到我们需要的节点转到了根节点处

旋转的过程也就是 xx 节点逐渐向根结点逼近的过程。那么我们每次旋转的时候去考虑将其旋转到它父节点的位置来向上逼近。

手玩一下可得，我们需要把从 xx 到根节点上 fa[x]fa[x] 连接的边都删掉，然后把 fa[x]fa[x] 连成 xx 的右儿子以维护BST性质，如果 xx 点存在右子树，那么就把它连到 fa[x]fa[x] 的左子树上，最后再更新一下 fa[fa[x]]fa[fa[x]] 的左儿子即可。

但是在 $ x、fa[x]、fa[fa[x]] $ 共线的情况下，如果仍然按照从下往上的顺序转，那么我们的链结构会被破坏从而导致失衡。此时就需要用双旋去平衡，其实也就是先转父节点再转子节点，最终就可以达到我们想要的结果。

最后不要忘了上传。

即

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
inline void rotate(int x)
{
    int fx = f[x], gfx = f[fx];
    int c = get(ix);
    f[x] = gfx;
    f[fx] = x;
    son[fx][c] = ch[x][c ^ 1];
    son[x][c ^ 1] = fx;
    if (son[x][c ^ 1])
        fa[son[x][c ^ 1]] = fx;
    if (gfx)
        son[gfx][get(fx)] = x;
    up(fx);
    up(x);
}

inline void Splay(int x)
{
    while (fa[x])
    {
        if (fa[fa[x]])
            rotate(get(x) == get(fa[x]) ? fa[x] : x);
        rotate(x);
    }
    rt = x;
    return;
}

那么接下来的操作就好说了，我们已经维护好了性质，只需要利用我们构建的优美的平衡结构即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
inline int rt_pre()
{
    int x = ls(rt);
    while (rs(x))
        x = rs(x);
    splay(x);
    return x;
}

inline int rt_nxt()
{
    int x = rs(x);
    while (ls(x))
        x = ls(x);
    splay(x);
    return x;
}

inline void insert(int x)
{
    int i = rt, f = 0;

    while (i and val[i] != x)
        f = i, i = son[i][x > val[i]];

    if (i)
        cnt[i]++;
    else
    {
        i = tot++;
        cnt[tot] = siz[tot] = 1;
        val[tot] = x;
        fa[tot] = f;
        if (f)
            son[f][x > cal[f]] = i;
    }

    up(i);
    up(fa[i]);

    if (!rt)
        rt = i;
    splay(i);

    return;
}

inline void erase(int x)
{
    int i = rt;
    while (i and val[i] != x)
        i = son[i][x > val[i]];

    if (!i)
        return;
    splay(i);

    if (!(--cnt[i]))
    {
        if (!ls(i) and !rs(i))
            clear(i), rt = 0;
        else if (!ls(i))
            rt = rs(i), fa[rt] = 0, clear(i);
        else if (!rs(i))
            rt = ls(i), fa[rt] = 0, clear(i);
        else
        {
            int p = rt_pre();
            rs(p) = rs(i);
            fa[rs(i)] = p;
            clear(i);
        }
    }

    up(rt);
}

inline int rk(int x)
{
    int res = 0, i = rt;
    while (i and val[i] != x)
    {
        if (x < val[i])
            i = ls(i);
        else
            res += siz[ls(i)] + cnt[i], i = rs(i);
    }

    res += siz[ls(i)];
    splay(i);
    return res + 1;
}

inline int kth(int k)
{
    int i = rt;
    while (i)
    {
        int lcnt = siz[ls(i)];
        if (lcnt < k and k <= lcnt + cnt[i])
            break;
        else if (k <= lcnt)
            i = ls(i);
        else
            k -= lcnt + cnt[i], i = rs(i);
    }

    splay(i);
    return val[i];
}

inline int getpre(int x)
{
    int res = (insert(x), rt_pre());
    erase(x);
    return val[res];
}

inline int getnxt(int x)
{
    int res = (insert(x), rt_nxt());
    erase(x);
    return val[res];
}

Treap

树与堆的结合。

利用了堆的性质保证了树结构的平衡，即层数达到期望 loglog 。

Treap的每个节点需要一个额外的权值作为优先级，去维护它作为堆的性质。因此整棵树不仅要符合BST的特性，也要满足父节点的额外权值大于两个子节点。

我们一般设此权值为 ordord ，且是随机生成，因此Treap是一种弱平衡的结构。

Treap有两种实现形式，我们一一讲解。

带旋Treap

是Treap的最初形式，用“左旋”与“右旋”去维护平衡，但它不支持区间操作。

我们去定义一些存储结构。

1
2
3
4
5
6
7
#define ls(x) son[x][0]
#define rs(x) son[x][1]
const int Maxn = 1e5 + 10;
int fa[Maxn], son[Maxn][2];
int val[Maxn], cnt[Maxn];
int siz[Maxn];
int ord[Maxn];

带旋的Treap常数较小且不容易卡，因为我们会对每一个节点去随机出来一个值作为堆的优先级，同时在每次删除或者插入时根据这个权值去决定旋转与否。

旋转：

我们需要在不影响树的性质的前提之下，把和旋转方向相反的子树变为根，把原来根结点作为与旋转方向相同的子节点，且左旋与右旋操作是相互的。

那么就根据堆的性质往上转即可，因为是小根堆，那么上面的优先级一定会更小。最终也就是让左子节点或者右子节点变为根结点即可。

        A                 C
       / \               / \
      B   C    ---->    A   E
         / \           / \
        D   E         B   D


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
inline void up(int x)
{
    return siz[x]=siz[ls(x)]+siz[rs(x)]+1,void();
}

inline void spin(int &i,int p)
{
    int t=s[i][p];
    s[i][p]=s[t][!p];
    s[t][!p]=i;
    up(i); up(t);
    i=t;

    return;
}

插入和普通的BST没啥太大区别，只需要注意要通过旋转来维护堆的性质。至于删除的话就大力分类讨论即可，考虑删除后谁适合当父节点，且要注意更改树的大小。

然后我们就可以再次利用构建的性质去进行操作。

注意从根结点开始递归。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
inline void ins(int x, int &i)
{
    if (!i)
    {
        i = ++tot;
        siz[i] = 1;
        val[i] = x, pri[i] = rand();
        return;
    }

    siz[i]++;
    if (x <= val[i])
    {
        ins(x, ls(i));
        if (pri[ls(i)] < pri[i])
            spin(i, 0);
    }
    else
    {
        ins(x, rs(i));
        if (pri[rs(i)] < pri[i])
            spin(i, 1);
    }

    return;
}

inline void del(int x, int &i)
{
    if (x == val[i])
    {
        if (ls(i) * rs(i) == 0)
        {
            i = son[i][0] + son[i][1];
            return;
        }
        if (pri[ls(i)] > pri[rs(i)])
        {
            spin(i, 1);
            del(x, ls(i));
        }
        else
        {
            spin(i, 0);
            del(x, rs(i));
        }
    }
    else if (val[i] > x)
        del(x, ls(i));
    else
        del(x, rs(i));

    up(i);

    return;
}

inline int rk(int x, int i)
{
    if (!i)
        return 1;
    if (val[i] >= x)
        return rk(x, ls(i));
    return rk(x, rs(i)) + siz[ls(i)] + 1;
}

inline int kth(int x, int i)
{
    if (siz[ls(i)] == x - 1)
        return w[i];
    if (siz[ls(i)] >= x)
        return ask(x, ls(i));

    return kth(x - siz[ls(i)] - 1, rs(i));
}

inline int pre(int x, int i)
{
    if (!i)
        return -inf;
    if (val[i] < x)
        return max(val[i], pre(x, rs(i)));
    else
        return pre(x, ls(i));
}

inline int nxt(int x, int i)
{
    if (!i)
        return inf;
    if (val[i] > x)
        return min(val[i], nxt(x, ls(i)));
    else
        return nxt(x, rs(i));
}

FHQ Treap

即无旋Treap。

现在我们不旋转了，换用分裂与合并去维护树的特性。

就是把树拆开，拼上，再拆开，再拼上。

那么我们需要存储五种信息，左右子树编号，权值，子树大小，索引。

分裂分为两种，分别为按值分裂与按大小分裂。

在通常情况下，FHQ仅发挥平衡树功能时，我们按值分裂，当维护区间信息时我们就需要去按照大小分裂，即文艺平衡树。

合并时就一种，即把两棵树合二为一，其中一树上的所有权值都需要小于另一棵待合并的树，以此来维持Treap的性质。

首先来说插入。

那么我们要插入它，肯定是按照插入值 valval 来分类，得到一棵权值全部大于它的树与另一棵权值全部小于它的树，那么我们直接合并 xx 和用 valval 新建的节点，最后并上 yy 就大功告成。

再说删除。

我们还是先按照 valval 分裂成两棵树 x,zx,z，再按照 val−1val-1 把其中一棵 xx 分裂为 x,yx,y。那么我们可以得到三棵树，此时 yy 上所有权值都会等于 valval。那么我们删除它的根结点，让 yy 等于合并 yy 的左子树与有字数，最后再合并上 x,yx,y。

前驱的话直接按照 val−1val-1 分裂，在xx里最右的数即为前驱。

后继同样，按照valval分裂，在yy中最左的数即为后继。

至于建树，我们发现Treap其实是笛卡尔树，那么我们直接利用笛卡尔树o(n)o(n)建树方法即可，即单调栈维护右链。

FHQ的区间操作

相比于带旋Treap来说，FHQ的一个特点就是可以实现各种区间操作。我们以文艺平衡树为例来介绍各种区间操作。

文艺平衡树的特别之处就是需要提供一个区间翻转操作，那么我们首先考虑去建树，建出来的树需要是我们最初始的区间。

那么我们只需要把区间下标以此地插入Treap，那么中序遍历之后我们就能方便地得到这个区间。

但是Treap还会根据堆的性质来调整树的结构，如何确保中序遍历正确输出就是我们亟需解决的一个问题。

其实我们还是可以参考笛卡尔树的单调栈建树方法来解决它。

那么我们设新插入的节点为xx，每一个新插入的节点一定会被连到Treap的右链中。

从根结点开始，右链上 ordord 显然是递增的，那么我们可在此链上找到第一个 ordord 大于 xx 节点，我们称之为 vv，并且把它替换成 xx。

又因为 xx 一定会大于树上的其它全部节点，我们需要把 vv及其子树作为 xx 的左子树，并且 xx 此时并没有右子树。

那么显然中序遍历时 xx 一定为最后一个被遍历的。

区间翻转

我们需要翻转 [l,r][l,r],那么基本思路是把树分裂成 $[1,l-1],[l,r],[r+1,n] $ 三个区间，再对中间的 [l,r][l,r] 进行翻转操作。

翻转的具体操作其实就是把区间内子树的每一个左右儿子都交换位置。

如图,就是翻转了上图的Treap：

如果翻转是这个方式，那么每次翻转区间时，都会有 r−lr-l 个区间被交换位置，时间复杂度会很高，如何处理？

我们回想一下在线段树遇到这种情况时是怎么处理的？显然，Lazy Tag即可解决问题。

我们只需要在父节点打上标记，那么就可以代表整课子树的左右子节点都要交换。

同时要注意我们应该在分裂时下传标记，又因合并需要分裂，那么合并前也需要下传。

那么，我们就是在树的结构改变时，我们需要进行分裂或者合并操作时，需要改变某个点的左右儿子信息时，操作之前也应下传标记。

没了。

（代码不是我的）

FHQ Treap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<bits/stdc++.h> 
using namespace std;
const int N=1e5+105;
int son[N][3],val[N],ran[N],siz[N],SIZE,n,root,x,y,z,opt,a;
void Up(int x){siz[x]=1+siz[son[x][0]]+siz[son[x][1]];} 
int New(int v){
	siz[++SIZE]=1;
	val[SIZE]=v;ran[SIZE]=rand();
	return SIZE;
}
int merge(int x,int y){
	if(!x||!y) return x+y;
	if(ran[x]<ran[y]){
		son[x][1]=merge(son[x][1],y);
		Up(x);return x;
	}
	else {
		son[y][0]=merge(x,son[y][0]);
		Up(y);return y;
	}
}
void split(int p,int k,int &x,int &y){
	if(!p) x=y=0;
	else{
		if(val[p]<=k) x=p,split(son[p][1],k,son[p][1],y);
		else y=p,split(son[p][0],k,x,son[p][0]);
		Up(p);
	}
}
int kth(int p,int k){
	while(1){
		if(k<=siz[son[p][0]])p=son[p][0];
		else if(k==siz[son[p][0]]+1) return p;
		else k-=siz[son[p][0]]+1,p=son[p][1];
	}
}
int main(){
	srand(1e9+7);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&opt,&a);
		if(opt==1){//插入 
			split(root,a,x,y);
			root=merge(merge(x,New(a)),y);
		}
		else if(opt==2){
			split(root,a,x,z);split(x,a-1,x,y);
			y=merge(son[y][0],son[y][1]);root=merge(merge(x,y),z);
		}
		else if(opt==3){
			split(root,a-1,x,y);
			printf("%d\n",siz[x]+1);
			root=merge(x,y);
		}
		else if(opt==4){printf("%d\n",val[kth(root,a)]);}
		else if(opt==5){
			split(root,a-1,x,y);
			printf("%d\n",val[kth(x,siz[x])]);
			root=merge(x,y);
		}
		else if(opt==6){
			split(root,a,x,y);
			printf("%d\n",val[kth(y,1)]);
			root=merge(x,y);
		}
	}
	return 0;
}

FHQ Treap区间操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<bits/stdc++.h> 
using namespace std;
const int N=1e5+105;
int son[N][3],val[N],ran[N],siz[N],SIZE,n,root,m;
bool f[N];
void Up(int x){siz[x]=1+siz[son[x][0]]+siz[son[x][1]];} 
void Down(int x){
	swap(son[x][0],son[x][1]);
	if(son[x][0])f[son[x][0]]^=1;
	if(son[x][1])f[son[x][1]]^=1;
	f[x]=0;
}
int New(int v){
	siz[++SIZE]=1;
	val[SIZE]=v;ran[SIZE]=rand();
	return SIZE;
}
int merge(int x,int y){
	if(!x||!y) return x+y;
	if(ran[x]<ran[y]){
		if(f[x])Down(x);
		son[x][1]=merge(son[x][1],y);
		Up(x);return x;
	}
	else {
		if(f[y])Down(y);
		son[y][0]=merge(x,son[y][0]);
		Up(y);return y;
	}
}
void split(int p,int k,int &x,int &y){
	if(!p) x=y=0;
	else{
		if(f[p])Down(p);//下面用siz，而不是val 
		if(siz[son[p][0]]<k) x=p,split(son[p][1],k-siz[son[p][0]]-1,son[p][1],y);
		else y=p,split(son[p][0],k,x,son[p][0]);
		Up(p);
	}
}
/*int kth(int p,int k){
	while(1){
		if(k<=siz[son[p][0]])p=son[p][0];
		else if(k==siz[son[p][0]]+1) return p;
		else k-=siz[son[p][0]]+1,p=son[p][1];
	}
}*/
void out(int x){
	if(!x) return ;
	if(f[x])Down(x);
	out(son[x][0]);
	printf("%d ",val[x]) ;
	out(son[x][1]);
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)root=merge(root,New(i));
	for(int i=1;i<=m;i++){
		int l,r,x,y,z;
		scanf("%d%d",&l,&r);
		split(root,l-1,x,y);split(y,r-l+1,y,z);
		f[y]^=1;root=merge(x,merge(y,z));
	}
	out(root);
	return 0;
}

没了。

动态树

LCT

如果我们需要维护一棵树，支持链上求和、链上求最值、链上修改、子树修改、子树求和，那么我们可以用树剖轻松地过掉。

那如果我们要额外支持换根、断边、连点这几个操作呢？显然树剖就不太够看了。因为树剖是静态的，不能加边或者删边。

怎么解决？LCT即可。

没错，就是LinkCutTree。

它用来解决动态树问题，即带修改边的树剖，其本质是利用虚实链剖分去维护。

一个节点最多会连出一条实边指向儿子，因此实边必定会聚成实链。那么根据树剖的思想，我们也需要一个数据结构去维护动态的东西——平衡树！

我们这里选用Splay去维护。

它与轻重链剖分最大的不同在于重链是偏静态的，但是偏路径是动态的。

LCT维护的对象本质上是一片森林，都是由纯虚边或者纯实边构成的纯种树。

由此LCT会有一些神奇的性质:
1.每一个Splay都是维护的一条从上到下的路径，且在原树中的深度会单调递增。那么显然，同一棵Splay中不会有同一层的节点，即一个父亲的儿子里最多只会存在一个在包含父亲的Splay中。
2.每个节点包含且仅包含于一个Splay中，即各个Splay的点集不存在交集。
3.实边会包含在Splay中，虚边总是由一棵Splay指向它中序遍历最靠前的点在原树里的父亲。

那么为了保持树的形态，我们要让父节点指向其它子节点的边为虚边，但是其它子节点会指向父节点，即认父不认子。

各种操作：

access(x)access(x)

为LCT核心操作，用来变换虚实边。

由于其性质3,我们并不能保证两个点路径会直接连通。那么我们此时就需要一个操作来打通树的任通二脉，让我们指定的节点之间存在一条通路。

那么accessaccess就应运而生了，它定义为打通根结点到指定节点的实链，使一个中序遍历从根结点开始，到指定节点停止的Spaly被构造。

我们放几个图（偷得：

这是树的开始状态，我们给他划分一下Splay：

假设我们需要把NN到AA打通，那么其他的链都要给它让路，也就是变成下图：

如何实现？模拟即可。

首先把NN变成根，再把原来N−ON-O的边变为虚边。又为了保证深度严格单调，我在Splay中OO在NN的右子树里，那么直接把NN的右子节点变为0：

之后再把其他碍事的玩意都干掉就行



好了，成功了。

代码实现也不难，只需要转到根，换子节点，更新，再把当前点切换为虚边指向的父节点即可。

1
2
3
4
5
6
inline void access(int x)
{
	for(int v=0;x;v=x,x=f[x])
		splay(x),rs(x)=v,up(x);
    return;
}

makeroot(x)makeroot(x)

仅仅把某条路径拉起来并不能实现我们的需求，那么我们需要得到两个节点之间的路径信息。

然而这俩点不一定是同一链上，那么我们可以换根，使指定的节点成为原树的根，就可以快速地利用性质处理了。

我们需要借助一下 access(x)access(x) 和Splay的翻转的操作来实现。

打通道路后xx一定是Splay中中序遍历的最后一个点，那么我们转上去后，xx在Splay里会没有右子树。那么我们翻转整个Splay，使得所有点的深度也翻转，xx没了左子树，就会变成深度最小的点，即根结点，那么就实现了换根的操作。

1
2
3
4
5
6
7
8
9
10
11
inline void reverse(int x)
{
    swap(ls(x),rs(x));
    tagr[x]^=1;//翻转的LazyTag
}
inline void makeroot(int x)
{
    access(x);
    splay(x);
    reverse(x);
}

findroot

即找某点所在树的根，主要用于判断两点是否连通。

1
2
3
4
5
6
7
8
inline int findroot(int x)
{
    access(x); 
    splay(x);
    while(ls(x))down(x),x=ls(x);
    splay(x);
    return x;
}

split

定义为从 x−>yx->y 拉出一条路径成为一个Splay。(这里让 yy 作为Splay的根，xx 作为原树的根)

1
2
3
4
5
6
7
inline void split(int x,int y)
{
    makeroot(x);
    access(y);
    splay(y);
    return;
}

那么路径就可以直接用 accessaccess 得到，而把 yy 转到Splay根之后，我们可以直接访问它来获得有关信息。

连边（使x−>yx->y，虚边）

1
2
3
4
5
6
7
8
inline bool link(int x,int y)
{
    makeroot(x);
    if(findroot(y)==x)
        return 0;
    f[x]=y;
    return 1;
}

这里布尔返回值是判断连边是否合法。

cut

断边。

如果保证合法，如下

1
2
3
4
5
6
7
inline void cut(int x,int y)
{
    split(x,y);
    f[x]=ls(y)=0;
    up(y);
    return;
}

如果不保证，我们会利用性质：

先判断连通性(xx变成根了)，再看是否有父子关系，再看 yy是否有左子节点。

因为在 access(y)access(y) 之后，如果两点在同一Splay但是没有直接的边，那么中间会有别的边，且中序遍历时 x,yx,y 直接会有别的边。

所以需要满足三个条件才可断。

1
2
3
4
5
6
7
8
9
inline bool cut(int x,int y)
{
	makeroot(x);
	if(findroot(y)!=x||f[y]!=x||ls(y))
        return 0;
	f[y]=rs(x)=0;//x在findroot(y)后被转到了根
	up(x);
	return 1;
}

那么LCT中的Splay操作也会有些细节不大寻常，可以用下面更稳妥的方法写：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void pushdown(int x)
{
    if(tagr[x])
    {
        if(ls(x))
            resver(ls(x));
        if(rs(x))
            resver(rs(x));
        tagr[x]=0;
    }
    return;
}
void makeroot(int x)
{
    access(x);
    splay(x);
    pushr(x);
}

基础操作没了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
#include <bits/stdc++.h>
using namespace std;
#ifdef ONLINE_JUDGE
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 21], *p1 = buf, *p2 = buf;
#endif
inline int read()
{
    int ret = 0, flag = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            flag = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
        ret = ret * 10 + c - '0', c = getchar();
    return ret * flag;
}
const int Maxn = 3e5 + 10;
#define ls(x) son[x][0]
#define rs(x) son[x][1]
int n, m;
int rt;
int son[Maxn][2];
int f[Maxn], val[Maxn];
int s[Maxn], st[Maxn];
int v[Maxn];
bool r[Maxn];
inline bool nrt(int x)
{
    return ls(f[x]) == x or rs(f[x]) == x;
}
inline void up(int x)
{
    s[x] = s[ls(x)] ^ s[rs(x)] ^ v[x];
    return;
}
inline void rev(int x)
{
    swap(ls(x), rs(x));
    r[x] ^= 1;
    return;
}
inline void down(int x)
{
    if (r[x])
    {
        if (ls(x))
            rev(ls(x));
        if (rs(x))
            rev(rs(x));
        r[x] = 0;
    }
    return;
}

inline void rotate(int x)
{
    int y = f[x], z = f[y];
    int k = (rs(y) == x), w = son[x][!k];
    if (nrt(y))
        son[z][rs(z) == y] = x;
    son[x][!k] = y;
    son[y][k] = w;
    if (w)
        f[w] = y;
    f[y] = x, f[x] = z;
    up(y);
    return;
}
inline void splay(int x)
{
    int y = x, t = 0;
    st[++t] = y;
    while (nrt(y))
        st[++t] = y = f[y];
    while (t)
        down(st[t--]);

    while (nrt(x))
    {
        y = f[x];
        t = f[y];
        if (nrt(y))
            rotate((ls(y) == x) ^ ((ls(t) == y)) ? x : y);
        rotate(x);
    }
    up(x);
}
inline void access(int x)
{
    for (register int y = 0; x; x = f[y = x])
    {
        splay(x), rs(x) = y;
        up(x);
    }
    return;
}
inline void makert(int x)
{
    access(x);
    splay(x);
    rev(x);
    return;
}
inline int findrt(int x)
{
    access(x);
    splay(x);
    while (ls(x))
        down(x), x = ls(x);
    splay(x);
    return x;
}
inline void split(int x, int y)
{
    makert(x);
    access(y);
    splay(y);
    return;
}
inline void link(int x, int y)
{
    makert(x);
    if (findrt(y) != x)
        f[x] = y;
    return;
}
inline void cut(int x, int y)
{
    makert(x);
    if (findrt(y) == x and f[y] == x and !ls(y))
    {
        f[y] = rs(x) = 0;
        up(x);
    }

    return;
}
inline void work()
{
    n = read();
    m = read();
    for (register int i = 1; i <= n; i++)
        v[i] = read();
    for (register int i = 1; i <= m; i++)
    {
        int opt = read();
        int x = read(), y = read();
        if (opt == 0)
            split(x, y), printf("%d\n", s[y]);
        else if (opt == 1)
            link(x, y);
        else if (opt == 2)
            cut(x, y);
        else if (opt == 3)
            splay(x), v[x] = y;
    }

    return;
}
int main()
{
    work();
    return 0;
}

线段树进阶 ---- 分裂与合并

使用前提：动态开点权值线段树

合并

我们在一些情况下需要去整合两棵权值线段树的信息，即为线段树合并。

其实线段树合并就是两个树相加，广义的相加，也就是对齐每一个点的位置进行权值的加减。

那么如何合并？

很简单的暴力就是 O(N)O(N) 枚举，不再阐述。

由于日常经验我们可能会想到使用启发式合并。但是显然会在有分裂操作时寄掉。

所以我们直接在线段树上递归处理。

假设我们需要合并的节点为 x,yx,y ，我们可以直接将yy上的信息加到xx上，用xx来表示我们合并出来的新树。同时我们为了节省空间也可以定义一个rubrub数组去存储我们合并后剩下的“废节点”，并且在动态开点的时候可以优先考虑使用里面的节点编号，这也就是空间回收。

分裂

可以类比FHQ Treap的分裂。

是线段树合并的逆过程。一般来说就是把一棵线段树按照至于分裂成两部分，即取出前 kk 大或者前 kk 小。

显然，线段树分裂也仅适用于有序的序列，这也就是为什么必须在权值线段树上进行分裂的原因。

暴力的方法显然，找到 kk 然后在后面的值新建一棵树，再把原树上对应的减去。

然而我们有更好的方法。去进行类似FHQ Treap的操作，我们可以优化至 $ O(log n) $ 。

如果目前需要把以 $ x $ 为根的树分为新的 $ x’,y $ 两棵树，以K为界限去分前k小，后面的在 $ y $ 里。

那么我们先看当前 $ x $ 的左子树值 vx1v_{x1} ，如果 $ v_{x1} < k $ ，那就左侧给 xx ，递归右侧即可，但注意此时的 kk 就会变成 k−vx1k-v_{x1} 。

如果 v==kv==k ，那么左边给 xx ，右边给 yy 。

在处理完结构后我们考虑权值分配， xx 的新权值毫无疑问是 kk ，那么 yy 权值也就是 xx 旧权值减去 kk 了。

那么如果 v>=kv>=k ，yy 的右儿子都是要赋值的。

没了。

那么以洛谷P5494为例子，就是简单的板子啦

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
#include<bits/stdc++.h>
using namespace std;
#define ls(x) son[x][0]
#define rs(x) son[x][1]
const int Maxn=200010;
int n,m;
int tot,cnt,sum=1;
int son[Maxn<<5][2];
int rt[Maxn];
ll val[Maxn<<5];
int rush[Maxn<<5];

inline int nrt()
{
	return ((cnt!=0)?rush[cnt--]:++tot);
}

inline void del(int p)
{
	rush[++cnt]=p;
	ls(p)=rs(p)=val[p]=0;
	return;
}

inline void cg(int &p,int l,int r,int pos,int k)
{
	p=((!p)?nrt():p);
	if(p==0)
		p=nrt();
	val[p]+=k;
	
	if(l==r)
		return;
	
	int mid=(l+r)>>1;
	if(pos<=mid)
		cg(ls(p),l,mid,pos,k);
	else
		cg(rs(p),mid+1,r,pos,k);
	
	return;
}

inline ll ask(int p,int l,int r,int L,int R)
{
	if(R<l or r<L)
		return 0;
	
	if(l>=L and r<=R)
		return val[p];
	
	int mid=(l+r)>>1;
	
	return ask(ls(p),l,mid,L,R)+ask(rs(p),mid+1,r,L,R);
}

inline int rk(int p,int l,int r,int k)
{
	if(l==r)
		return l;
	
	int mid=(l+r)>>1;
	
	if(val[ls(p)]>=k)
		return rk(ls(p),l,mid,k);
	else
		return rk(rs(p),mid+1,r,k-val[ls(p)]);
}

inline int merge(int x,int y)
{
	if(x==0 or y==0)
		return x+y;
	
	val[x]+=val[y];
	ls(x)=merge(ls(x),ls(y));
	rs(x)=merge(rs(x),rs(y));
	del(y);
	
	return x;
}

inline void split(int x,int &y,ll k)
{
	if(x==0)
		return;

	y=nrt();

	ll v=val[ls(x)];
	
	if(k>v)
		split(rs(x),rs(y),k-v);
	else
		swap(rs(x),rs(y));
	
	if(k<v)	
		split(ls(x),ls(y),k);
	
	val[y]=val[x]-k;
	val[x]=k;
	
	return;
}

inline void work()
{
    read(n);
    read(m);
	
	for(register int i=1;i<=n;i++)
	{
        int x;
        read(x);
		cg(rt[1],1,n,i,x);
	}
	
	for(register int i=1;i<=m;i++)
	{
        int opt;
        read(opt);
		if(opt==0)
		{
			int x,y,z;
            read(x),read(y),read(z);
			ll k1=ask(rt[x],1,n,1,z);
			ll k2=ask(rt[x],1,n,y,z);
			int tmp=0;
			split(rt[x],rt[++sum],k1-k2);
			split(rt[sum],tmp,k2);
			rt[x]=merge(rt[x],tmp);
		}
		else if(opt==1)
		{
			int x,y;
            read(x); read(y);
			rt[x]=merge(rt[x],rt[y]);
		}
		else if(opt==2)
		{
			int x,y,z;
            read(x),read(y),read(z);
			cg(rt[x],1,n,z,y);
		}
		else if(opt==3)
		{
			int x,y,z;
            read(x),read(y),read(z);
            print(ask(rt[x],1,n,y,z)),cout<<endl;
		}
		else 
		{
			int x,y;
            read(x),read(y);
			if(val[rt[x]]<y)
				print("-1"),cout<<endl;
			else
                print(rk(rt[x],1,n,y)),putchar('\n');
		}
	}
		
	return;
}

signed main(void)
{
	work();
	return 0;
}
Ztemily

Ztemily

此后如竟没有炬火，我们便是唯一的光。

6
0
1
NOTICE

新搭建的博客，欢迎来玩~

CATEGORYS
TAGS
OI