Caiwen的博客

下列的文章正在处于草稿状态，尚未完成。

平衡树

2025-03-03 11:59:03

题目

P4008 [NOI2003] 文本编辑器

https://www.luogu.com.cn/problem/P4008

题目描述

实现一个文本编辑器，有如下操作：

将光标移动到某个位置
在光标后插入一个字符串
删除光标后若干字符
获取光标后若干字符
光标向前移动
光标向后移动

笔记

cpp
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
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define ls(k) (k)<<1
#define rs(k) (k)<<1|1
#define il inline
#define debug(x) cout<<#x<<"="<<x<<endl
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
const int mod=0;
typedef pair<int,int> pii;
#define _ 1024*1024*2
struct FHQ{
    int tot=0;
    struct Node{int ls,rs,dat,siz;char val;} tree[_];
    #define nt tree[k]
    #define lt tree[tree[k].ls]
    #define rt tree[tree[k].rs]
    il void update(int k){nt.siz=1+lt.siz+rt.siz;}
    il int create(char v){int k=++tot;nt.dat=rand(),nt.val=v,nt.siz=1;return tot;}
    il int merge(int x,int y){
        if(!x||!y) return x+y;
        if(tree[x].dat<tree[y].dat) return tree[x].rs=merge(tree[x].rs,y),update(x),x;
        else return tree[y].ls=merge(x,tree[y].ls),update(y),y;
    }
    void split(int k,int x,int &l,int &r){
        if(!k) return l=r=0,void();
        if(lt.siz+1<=x) l=k,split(nt.rs,x-lt.siz-1,nt.rs,r);
        else r=k,split(nt.ls,x,l,nt.ls);
        update(k);
    }
    void print(int k){// 中序遍历打印
        if(k==0) return;
        print(nt.ls);cout<<nt.val;print(nt.rs);
    }
} tree;
inline void subtask(){
    srand(time(NULL));
    int pos=0,root=0,n,l,r;cin>>n;
    while(n--){
        char op[7];cin>>op;
        if(op[0]=='M') cin>>pos;
        if(op[0]=='I'){
            int len;cin>>len;
            tree.split(root,pos,l,r);
            for(int i=1;i<=len;i++){
                char ch=getchar();
                while(ch<32||ch>126) ch=getchar();
                l=tree.merge(l,tree.create(ch));
            }
            root=tree.merge(l,r);
        }
        if(op[0]=='D'){
            int len,tmp;cin>>len;
            tree.split(root,pos+len,l,r);tree.split(l,pos,l,tmp);
            root=tree.merge(l,r);
        }
        if(op[0]=='G'){
            int len,tmp;cin>>len;
            tree.split(root,pos+len,l,r);tree.split(l,pos,l,tmp);
            tree.print(tmp);cout<<endl;
            root=tree.merge(tree.merge(l,tmp),r);
        }
        if(op[0]=='P') pos--;
        if(op[0]=='N') pos++;
    }
}
signed main(){
    int t=1;//cin>>t;
    while(t--) subtask();
    return 0;
}

P3391 【模板】文艺平衡树

https://www.luogu.com.cn/problem/P3391

题目描述

维护一个序列，有若干区间翻转操作，输出所有操作后，得到的序列

笔记

对区间 $[l,r]$ 进行翻转，可以视为将区间 $[l,k]$ 和区间 $[k+1,r]$ 交换，然后这两个区间再分别递归进行这个操作

也可以视为找到一个轴 $k(l<k<r)$ ，将区间 $[l,k-1]$ 和 $[k+1,r]$ 交换，然后这两个区间再分别递归进行这个操作

然后对于本题我们在 fhq treap 上引入懒标记，每次分裂或者合并时 pushdown 这个懒标记

cpp
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
#include<iostream>
#define maxn 100005
using namespace std;

int id,val[maxn],dat[maxn],size[maxn],ch[maxn][2],root,tag[maxn];
inline int create(int x){
	id++;
	val[id]=x;
	dat[id]=rand();
	size[id]=1;
	return id;
}
inline void pushup(int k){
	size[k]=size[ch[k][0]]+1+size[ch[k][1]];
}
inline void pushdown(int k){
	if(tag[k]){
		tag[ch[k][0]]^=1;
		tag[ch[k][1]]^=1;
		swap(ch[k][0],ch[k][1]);
		tag[k]=0;
	}
}
void split(int now,int k,int &x,int &y){
	if(!now) x=y=0;
	else{
		pushdown(now);
		int u=size[ch[now][0]]+1;
		if(u<=k){
			x=now;
			split(ch[now][1],k-u,ch[now][1],y);
			pushup(x);
		}else{
			y=now;
			split(ch[now][0],k,x,ch[now][0]);
			pushup(y);
		}
	}
}
int merge(int x,int y){
	if(!x||!y) return x+y;
	pushdown(x);
	pushdown(y);
	if(dat[x]<=dat[y]){
		ch[x][1]=merge(ch[x][1],y);
		pushup(x);
		return x;
	}else{
		ch[y][0]=merge(x,ch[y][0]);
		pushup(y);
		return y;
	}
}
void reverse(int l,int r){
	int p1=0,p2=0,p3=0,p4=0;
	split(root,l-1,p1,p2);
	split(p2,(r-l+1),p3,p4);
	tag[p3]^=1;
	p2=merge(p3,p4);
	root=merge(p1,p2);
}
void print(int k){
	pushdown(k);
	if(ch[k][0]) print(ch[k][0]);
	cout<<val[k]<<" ";
	if(ch[k][1]) print(ch[k][1]);
}

int main(){
	int n,m;
	cin>>n>>m;
	int l,r;
	for(int i=1;i<=n;i++){
		//int k;
		//cin>>k;
		split(root,i-1,l,r);
		root=merge(merge(l,create(i)),r);
	}
	while(m--){
		cin>>l>>r;
		reverse(l,r);
	}
	print(root);
	return 0;
}

P5055 【模板】可持久化文艺平衡树

https://www.luogu.com.cn/problem/P5055

题目描述

每次操作创建一个新版本。然后有如下的操作，可以基于之前的版本进行修改：

在某个位置插入一个数
删除某个位置上的数字
翻转区间
查询区间和

笔记

考虑创建新版本时，很多节点是和上一个版本是重合的，所以我们对于重合的点，直接重用，只产生新的发生改变的点。每次 pushdown 和 split 的时候克隆

至于节点数组开多大，直接估计比较麻烦，我们可以直接根据题目的空间的限制尽可能开大

cpp
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
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define ls(k) (k)<<1
#define rs(k) (k)<<1|1
#define debug(x) cout<<#x<<"="<<x<<endl
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
const int mod=0;
typedef pair<int,int> pii;
#define _ 200005
struct FHQ{
    struct Node{int ls,rs,val,dat,siz,lazy,sum;} tree[_<<6];
    int tot=0;
    #define nt tree[k]
    #define lt tree[tree[k].ls]
    #define rt tree[tree[k].rs]
    inline int create(int v){int k=++tot;nt.dat=rand(),nt.siz=1,nt.sum=v,nt.val=v;return tot;}
    inline int clone(int k){tree[++tot]=nt;return tot;}
    inline void update(int k){nt.siz=1+lt.siz+rt.siz,nt.sum=lt.sum+rt.sum+nt.val;}
    void pushdown(int k){
        if(!nt.lazy) return;
        if(nt.ls) nt.ls=clone(nt.ls);
        if(nt.rs) nt.rs=clone(nt.rs);
        swap(nt.ls,nt.rs);
        lt.lazy^=1,rt.lazy^=1;
        nt.lazy=0;
    }
    void split(int k,int x,int &l,int &r){
        if(!k) return l=r=0,void();
        pushdown(k);
        if(lt.siz+1<=x) l=clone(k),split(tree[l].rs,x-lt.siz-1,tree[l].rs,r),update(l);
        else r=clone(k),split(tree[r].ls,x,l,tree[r].ls),update(r);
    }
    int merge(int l,int r){
        if(l==0||r==0) return l+r;
        pushdown(l);pushdown(r);
        if(tree[l].dat<tree[r].dat) return tree[l].rs=merge(tree[l].rs,r),update(l),l;
        else return tree[r].ls=merge(l,tree[r].ls),update(r),r;
    }
} tree;
int root[_];
inline void subtask(){
    srand(time(NULL));
    int now=0,l,r,tmp,lastans=0,n;cin>>n;
    while(n--){
        int v,op;cin>>v>>op;
        if(op==1){
            int p,x;cin>>p>>x;p^=lastans,x^=lastans;
            tree.split(root[v],p,l,r);
            root[++now]=tree.merge(tree.merge(l,tree.create(x)),r);
        }
        if(op==2){
            int p;cin>>p;p^=lastans;
            tree.split(root[v],p,tmp,r);
            tree.split(tmp,p-1,l,tmp);
            root[++now]=tree.merge(l,r);
        }
        if(op==3){
            int x,y;cin>>x>>y;x^=lastans,y^=lastans;
            tree.split(root[v],y,l,r);
            tree.split(l,x-1,l,tmp);
            tree.tree[tmp].lazy^=1;
            root[++now]=tree.merge(tree.merge(l,tmp),r);
        }
        if(op==4){
            int x,y;cin>>x>>y;x^=lastans,y^=lastans;
            tree.split(root[v],y,l,r);
            tree.split(l,x-1,l,tmp);
            lastans=tree.tree[tmp].sum;
            cout<<lastans<<endl;
            root[++now]=tree.merge(tree.merge(l,tmp),r);
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    int t=1;//cin>>t;
    while(t--) subtask();
    return 0;
}

最后更新于：2025-04-03 13:04:25

Caiwen

本文作者

一只蒟蒻，爱好编程和算法

推荐文章

目录