Criska

Treap

写Treap写到吐啊……
好吧，学完Treap就把splay忘光了，两者到底有什么区别呢？

先上模板

普通平衡树

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
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
int n,size,root,ans;
struct node{
	int l,r,v,size,rnd,w;
}tr[200005];
inline int update(int k)
{
	tr[k].size=tr[tr[k].l].size+tr[tr[k].r].size+tr[k].w;
}
inline int rturn(int &k)
{
	int t=tr[k].l;
	tr[k].l=tr[t].r;
	tr[t].r=k;
	tr[t].size=tr[k].size;
	update(k);
	k=t;
}
inline int lturn(int &k)
{
	int t=tr[k].r;
	tr[k].r=tr[t].l;
	tr[t].l=k;
	tr[t].size=tr[k].size;
	update(k);
	k=t;
}
inline void insert(int &k,int x)
{
	if(!k)
	{
		size++;
		k=size;
		tr[k].w=tr[k].size=1;
		tr[k].rnd=rand();
		tr[k].v=x;
		return ;
	}
	tr[k].size++;
	if(tr[k].v==x) tr[k].w++;
	else 
	{
		if(tr[k].v<x)
		{
			insert(tr[k].r,x);
			if(tr[k].rnd>tr[tr[k].r].rnd) lturn(k);
		}
		else
		{
			insert(tr[k].l,x);
			if(tr[k].rnd>tr[tr[k].l].rnd) rturn(k);
		}
	}	
}
inline void del(int &k,int x)
{
	if(!k) return ;
	if(tr[k].v==x)
	{
		if(tr[k].w>1)
		{
			tr[k].size--;
			tr[k].w--;
			return ;
		}
		else
		{
			if(tr[k].l*tr[k].r==0) k=tr[k].l+tr[k].r;
			else
				if(tr[tr[k].l].rnd>tr[tr[k].r].rnd)
				{
					lturn(k); 
					del(k,x);
				}
				else
				{
					rturn(k); 
					del(k,x);
				}
		}
	}
	else
		if(x>tr[k].v) tr[k].size--,del(tr[k].r,x);
		else tr[k].size--,del(tr[k].l,x);
}
inline int find(int k,int x)
{
	if(k==0) return 0;
	if(tr[k].v==x) return tr[tr[k].l].size+1;
	else
		if(x>tr[k].v) return tr[tr[k].l].size+tr[k].w+find(tr[k].r,x);
		else return find(tr[k].l,x);
}
inline int num(int k,int x)
{
	if(k==0) return 0;
	if(x<=tr[tr[k].l].size)
		return num(tr[k].l,x);
	else 
		if(x>tr[tr[k].l].size+tr[k].w)
		return num(tr[k].r,x-tr[tr[k].l].size-tr[k].w);
		else return tr[k].v;
}
inline int pro(int k,int x)
{
	if(k==0) return 0;
	if(tr[k].v<x)
	{
		ans=k;
		pro(tr[k].r,x);
	}
	else pro(tr[k].l,x);
}
inline int succ(int k,int x)
{
	if(k==0) return 0;
	if(tr[k].v>x)
	{
		ans=k;
		succ(tr[k].l,x);
	}
	else succ(tr[k].r,x);
}
int main()
{
	scanf("%d",&n);
	int x,a;
	while(n--)
	{
        scanf("%d%d",&a,&x);
		if(a==1) insert(root,x);
		if(a==2) del(root,x);
		if(a==3) printf("%d\n",find(root,x));
		if(a==4) printf("%d\n",num(root,x));
		if(a==5) pro(root,x),printf("%d\n",tr[ans].v);
		if(a==6) succ(root,x),printf("%d\n",tr[ans].v);	
	}
	return 0;
}

[HNOI2002]营业额统计

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
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
int root,ans,n,size,sum=0,mark=0;
struct node{
	int l,r,v,size,w,rnd;
}t[200005];
inline int minn(int a,int b)
{
	if(a<b)return a;
	else return b;
}
inline int update(int k)
{
	t[k].size=t[t[k].l].size+t[t[k].r].size+t[k].w;
}
inline int lturn(int &k)
{
	int tt=t[k].r;
	t[k].r=t[tt].l;
	t[tt].l=k;
	t[tt].size=t[k].size;
	update(k);
	k=tt;
}
inline int rturn(int &k)
{
	int tt=t[k].l;
	t[k].l=t[tt].r;
	t[tt].r=k;
	t[tt].size=t[k].size;
	update(k);
	k=tt;
}
inline void insert(int &k,int x)
{
	if(!k)
	{
		size++;
		k=size;
		t[k].v=x;
		t[k].size=t[k].w=1;
		t[k].rnd=rand();
		return ;
	}
	t[k].size++;
	if(t[k].v==x) t[k].w++;
	else
		if(x>t[k].v)
		{
			insert(t[k].r,x);
			if(t[t[k].r].rnd<t[k].rnd)
				lturn(k);
		}
		else
		{
			insert(t[k].l,x);
			if(t[t[k].l].rnd<t[k].rnd)
				rturn(k);
		}
}
inline int pro(int k,int x)
{
	if(k==0) return 0;
	if(x>t[k].v)
	{
		ans=k; pro(t[k].r,x);
	}
	else pro(t[k].l,x);
}
inline int succ(int k,int x)
{
	if(k==0) return 0;
	if(x<t[k].v)
	{
		ans=k; succ(t[k].l,x);
	}
	else succ(t[k].r,x);
}
inline void find(int &k,int x)
{
	if(k==0) return ;
	if(t[k].v==x) 
	{
		if(t[k].w>1) mark=1;
		return ;
	}
	else
	{
		if(t[k].v>x) find(t[k].l,x);
		else find(t[k].r,x);
	}
}
int main()
{
	scanf("%d",&n);
	int x,a,b;
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&x);
		insert(root,x);		
		if(i==1)
		{
			sum+=x;
			continue;
		}
		pro(root,x);
		a=t[ans].v-x;
		if(a<0) a=-a;
		if(ans==0) a=999999999;
		succ(root,x);
		b=t[ans].v-x;
		if(b<0) b=-b;
		if(ans==0) b=999999999;
		mark=0;
		find(root,x);
		if(mark==1) continue;
		sum+=minn(a,b);
	}
	printf("%d",sum);
	return 0;
}

[NOI2004]郁闷的出纳员

好像有10分没拿到…………不管了…………拿90分走人= =

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
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
int n,mn,size,root,mm=0,sum=0;
struct node{
	int l,r,v,size,w,rnd;
}t[200005];
inline int update(int k)
{
	t[k].size=t[t[k].l].size+t[t[k].r].size+t[k].w;
}
inline int lturn(int &k)
{
	int tt=t[k].r;
	t[k].r=t[tt].l;
	t[tt].l=k;
	t[tt].size=t[k].size;
	update(k);
	k=tt;
}
inline int rturn(int &k)
{
	int tt=t[k].l;
	t[k].l=t[tt].r;
	t[tt].r=k;
	t[tt].size=t[k].size;
	update(k);
	k=tt;
}
inline void insert(int &k,int x)
{
	if(!k)
	{
		size++;
		k=size;
		t[k].size=t[k].w=1;
		t[k].rnd=rand();
		t[k].v=x;
		return ;
	}
	t[k].size++;
	if(x==t[k].v) t[k].w++;
	else
	{
		if(x>t[k].v)
		{
			insert(t[k].r,x);
			lturn(k);
		}
		else
		{
			insert(t[k].l,x);
			rturn(k);
		}
	}
}
inline int find(int k,int x)
{
	if(k==0) return 0;
	if(t[t[k].l].size>=x)
		return find(t[k].l,x);
	else 
		if(x>t[t[k].l].size+t[k].w)
		return find(t[k].r,x-t[t[k].l].size-t[k].w);
		else return t[k].v;		
}
inline void del(int &k)
{
	if(k==0) return ;
	if(t[k].v+mm>=mn)
	{
		del(t[k].l);
		update(k);
	}
	else
	{
		k=t[k].r;
		del(k);
	}	
}
int main()
{
	scanf("%d%d",&n,&mn);
	char s[1];
	int x;
	while(n--)
	{
		scanf("%s%d",s,&x);
		if(s[0]=='I') if(x>=mn) insert(root,x-mm),sum++;
		if(s[0]=='A') mm+=x;
		if(s[0]=='S') mm-=x,del(root);
		if(s[0]=='F') 
		{
			x=t[root].size-x+1;
			if(x<=0) 
			{
				cout<<-1<<endl;
				continue;
			}
			int y=find(root,x);
			if(y==0) y=-1;
			printf("%d\n",y+mm);
		}
	}
	printf("%d",sum-t[root].size);
	return 0;
}