Fork me on GitHub

Treap/Splay/Scapegoat 学习笔记&板子

发表于 | 分类于
字数统计: 1,876字 | 阅读时长 ≈ 11分钟

Treap/Splay/Scapegoat板子

全指针 毕竟指针好写好调（虽然占多了点M

Treap(LUOGU P3369/BZOJ 3224可食用)

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
// m     操作有m个
// 1 x   插入元素x
// 2 x   删除元素x。如果成功，输入1，否则输出0
// 3 k   输出值x的“名次”，即比x小的结点个数加1
// 4 x   第k小元素。k=1为最小元素
// 5 x   prefix of x
// 6 x   suffix of x
// ... to be continued ...
#include<bits/stdc++.h>
using namespace std;
struct Node {
	Node *ch[2]; // 左右子树
	int r; // 随机优先级
	int v; // 值
	int s; // 结点总数
	Node(int v = 0):v(v) {
		ch[0] = ch[1] = NULL;
		r = rand();
		s = 1;
	}
	int cmp(int x) const {
		if (x == v) return -1;
		return x < v ? 0 : 1;
	}
	void maintain() {
		s = 1;
		if(ch[0] != NULL) s += ch[0]->s;
		if(ch[1] != NULL) s += ch[1]->s;
	}
};
void rotate(Node* &o, int d) {
	Node* k = o->ch[d^1];
	o->ch[d^1] = k->ch[d];
	k->ch[d] = o;
	o->maintain();
	k->maintain();
	o = k;
}
void insert(Node* &o, int x) {
	if(o == NULL) o = new Node(x);
	else {
		int d = (x < o->v ? 0 : 1);
		insert(o->ch[d], x);
		if(o->ch[d]->r > o->r) rotate(o, d^1);
	}
	o->maintain();
}
Node* find(Node* o, int x) {
	if(o == NULL) return NULL;
	if(x == o->v) return o;
	return x < o->v ? find(o->ch[0], x) : find(o->ch[1], x);
}
void remove(Node* &o, int x) {
	int d = o->cmp(x);
	if(d == -1) {
		Node* u = o;
		if(o->ch[0] != NULL && o->ch[1] != NULL) {
			int d2 = (o->ch[0]->r > o->ch[1]->r ? 1 : 0);
			rotate(o, d2);
			remove(o->ch[d2], x);
		} else {
			if(o->ch[0] == NULL) o = o->ch[1];
			else o = o->ch[0];
			delete u;
		}
	} else
		remove(o->ch[d], x);
	if(o != NULL) o->maintain();
}
int kth(Node* o, int k) {
	if(o == NULL || k <= 0 || k > o->s) return 0;
	int s = (o->ch[0] == NULL ? 0 : o->ch[0]->s);
	if(k == s+1) return o->v;
	else if(k <= s) return kth(o->ch[0], k);
	else return kth(o->ch[1], k-s-1);
}
int rank(Node* o, int x) {
	if(o == NULL) return 1;
	if(x <= o->v) return rank(o->ch[0], x);
	return rank(o->ch[1], x) + (o->ch[0] == NULL ? 0 : o->ch[0]->s) + 1;
}
int prefix(Node *o, int k,int c) {
	if (o == NULL) return c;
	if (k > o->v) return prefix(o->ch[1],k,o->v);
	else return prefix(o->ch[0],k,c);
}
int suffix(Node *o, int k,int c) {
	if (o == NULL) return c;
	if (k < o->v) return suffix(o->ch[0],k,o->v);
	else return suffix(o->ch[1],k,c);
}
const int INF = INT_MAX >> 1;
/*
void dfs(Node *o)
{
	if (o == NULL) return ;
	printf("%d\n",o->v);
	 printf("LC of %d:\n",o->v);dfs(o->ch[0]);
	 printf("RC of %d:\n",o->v); dfs(o->ch[1]);
	printf("EO %d!\n\n",o->v); 
}
*/
int main(int argc, char *argv[]) {
	srand(int(time(NULL)));
	int m, c, v;
	Node* root = new Node(INF);
	scanf("%d", &m);
	while(m--) 
	{
		scanf("%d%d", &c, &v);
		if(c == 1) insert(root, v);
		else if(c == 2) {
			Node* o = find(root, v);
			if(o != NULL) remove(root, v);
		} else if(c == 3) printf("%d\n", rank(root, v));
		else if(c == 4) printf("%d\n", kth(root,v));
		else if(c == 5) printf("%d\n",prefix(root,v,0));
		else printf("%d\n",suffix(root,v,0));
	}
	return 0;
}

Splay(LUOGU P3391/BZOJ 3223可食用)

(好像叫Spaly的也有 大雾)

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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10; 
struct Node {
	Node* ch[2];
	int v,s,flip;
	int cmp(int k) {
		int d=k-ch[0]->s;
		if(d==1) return -1;
		return d<=0? 0:1;
	}
	void maintain() {
		s=ch[0]->s+ch[1]->s+1;
	}
	void pushdown() {
		if(flip) {
			flip=0;
			swap(ch[0],ch[1]);
			ch[0]->flip^=1;
			ch[1]->flip^=1;
		}
	}
};
Node* null=new Node();
void rotate(Node* &o,int d) {
	Node* k=o->ch[d^1];
	o->ch[d^1]=k->ch[d];
	k->ch[d]=o;
	o->maintain(),k->maintain();
	o=k;
}
void splay(Node* &o,int k) {
	o->pushdown();
	int d=o->cmp(k);
	if(d==1) k-=o->ch[0]->s+1;
	if(d!=-1) {
		Node* p=o->ch[d];
		p->pushdown();
		int d2=p->cmp(k);
		int k2=d2==0? k:k-p->ch[0]->s-1;
		if(d2!=-1) {
			splay(p->ch[d2],k2);
			if(d==d2) rotate(o,d^1);
			else rotate(o->ch[d],d);
		}
		rotate(o,d^1);
	}
}
Node* merge(Node* left,Node* right) {
	splay(left,left->s);
	left->ch[1]=right,left->maintain();
	return left;
}
void split(Node* o,int k,Node* &left,Node* &right) {
	splay(o,k);
	left=o,right=left->ch[1],left->ch[1]=null;
	left->maintain();
}
struct SplaySequence {
	int n;
	Node seq[maxn];
	Node* root;

	Node* build(int sz) {
		if(!sz) return null;
		Node* l=build(sz/2);
		Node* o=&seq[++n];
		o->v=n;
		o->ch[0]=l;
		o->ch[1]=build(sz-sz/2-1);
		o->flip=o->s=0;
		o->maintain();
		return o;
	}
	void init(int sz) {
		n=null->s=0;
		root=build(sz);
	}
} spaly;
vector<int> ans;
void print(Node* o) {
	if(o!=null) {
		o->pushdown();
		print(o->ch[0]);
		ans.push_back(o->v);
		print(o->ch[1]);
	}
}

int read() {
	char c=getchar();
	while(!isdigit(c)) c=getchar();
	int x=0;
	while(isdigit(c)) {
		x=x*10+c-'0';
		c=getchar();
	}
	return x;
}
int n,m;
int main(int argc, char *argv[]) 
{
	n=read(),m=read();
	spaly.init(n+1);   
	int l,r;
	Node *left,*right,*mid;
	while(m--) {
		l=read(),r=read();
		split(spaly.root,l,left,right);
		split(right,r-l+1,mid,right);
		mid->flip^=1;
		spaly.root = merge(merge(left,mid),right);
	}
	print(spaly.root);
	for(int i=1; i<ans.size(); i++) printf("%d ",ans[i]-1);
	return 0;
}

Scapegoat(LUOGU P3369/BZOJ 3224可食用)

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
#include<bits/stdc++.h>
#include<vector>
using namespace std;
const double alpha=0.7;

struct scapegoat{
    scapegoat *l,*r;
    int val,size,cnt;
    bool deleted;
    bool is_bad(){return (l->cnt > alpha*cnt+5 || r->cnt > alpha*cnt+5);}
    void maintain(){size=!deleted+l->size+r->size; cnt=1+r->cnt+l->cnt;}
};
scapegoat *null;

void dfs(scapegoat *o,vector<scapegoat*> &v)
{
    if(o == null) return;
    dfs(o->l,v);
    if(!o->deleted) v.push_back(o);
    dfs(o->r,v);
    if(o->deleted) delete o;
}
scapegoat *build(vector<scapegoat*> &v,int l,int r)
{
    if(l >= r) return null;
    int mid = (l+r) >> 1;
    scapegoat *o = v[mid];
    o->l = build(v,l,mid);
    o->r = build(v,mid+1,r);
    o->maintain();
    return o;
}
void rebuild(scapegoat* &o)
{
    vector<scapegoat*> v;
    dfs(o,v);
    o = build(v,0,v.size());
}
void insert(int x,scapegoat* &o)
{
    if(o==null)
    {
        o=new scapegoat;
        o->l=o->r=null;
        o->deleted=false;
        o->size=o->cnt=1;
        o->val=x;
        return;
    }
    else
    {
        ++o->size;
        ++o->cnt;
        if(x>=o->val)
            insert(x,o->r);
            else
            insert(x,o->l);
        if(o->is_bad())rebuild(o);
    }
}
int rank(scapegoat *now,int x)
    {
        int ans=1;
        while(now!=null)
        {
            if(now->val>=x)now=now->l;
            else
            {
                ans+=now->l->size+!now->deleted;
                now=now->r;
            }
        }
        return ans;
    }
int kth(scapegoat *now,int x)
{
    while(now!=null)
    {
        if(!now->deleted && now->l->size+1==x)
            return now->val;
        if(now->l->size>=x)now=now->l;
            else
            {
                x-=now->l->size+!now->deleted;
                now=now->r;
            }
    }
}
void erase(scapegoat *o,int rk)
{
    if(!o->deleted && rk==o->l->size+1)
    {
        o->deleted=1;
        --o->size;
        return;
    }
    --o->size;
    if(rk<=o->l->size+!o->deleted)
        erase(o->l,rk);
    else
        erase(o->r,rk-o->l->size-!o->deleted);
}
inline void read(int &a)
{
    int negativ = 1;
    a = 0;
    char c = getchar();
    while(!isdigit(c)){if(c == '-') negativ = -1; c = getchar();} 
    while(isdigit(c)) {a = a*10+c-'0';c = getchar();}
    a *= negativ;
}

scapegoat *root;
int main(int argc, char *argv[])
{
    null = new scapegoat;
    root = null;
    int n;
    read(n);
    while(n--)
    {
        int op,x;
        read(op); read(x);
        if(op==1)insert(x,root);
        if(op==2)erase(root,rank(root,x));
        if(op==3)printf("%d\n",rank(root,x));
        if(op==4)printf("%d\n",kth(root,x));
        if(op==5)printf("%d\n",kth(root,rank(root,x)-1));
        if(op==6)printf("%d\n",kth(root,rank(root,x+1)));
    }
    return 0; 
}