Splay模板 codevs1296&&codevs1286好郁闷

Posted by Cww97 on 2016-05-30

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/51535115
先存个板(未完全测试

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
#include<cstdio>
#include<algorithm>
using namespace std;

struct Node{
int key;//size
Node *l,*r,*f;//left,right,father
};
class SplayTree{
public:
void Init(){rt=NULL;}
void Zag(Node *x){//left rotate
Node *y=x->f;//y is the father of x
y->r = x->l;
if (x->l)x->l->f = y;//if x has left child
x->f =y->f;
if (y->f){//y is not root
if (y==y->f->l)y->f->l=x;//y if left child
else y->f->r=x;//y is right child
}
y->f=x;
x->l=y;
}

void Zig(Node *x){//right rotate
Node *y=x->f;//y is the father of x
y->l = x->r;
if (x->r)x->r->f=y;
x->f = y->f;
if (y->f){
if (y==y->f->l)y->f->l=x;
else y->f->r=x;
}
y->f=x;
x->r=y;
}

void Splay(Node *x){
while (x->f){
Node *p=x->f;
if (!p->f){
if (x==p->l)Zig(x);
else Zag(x);
}else if (x==p->l){
if (p==p->f->l){Zig(p);Zig(x);}
else {Zig(x);Zag(x);}
}else {//x==p->r
if (p==p->f->r){Zag(p);Zag(x);}
else {Zag(x);Zig(x);}
}
}
rt=x;
}

Node *Find(int x){
Node *T=rt;
while (T){
if (T->key==x){Splay(T);return T;}
else if (x<T->key)T=T->l;
else T=T->r;
}
return T;
}

void Insert(int x){
Node *T=rt,*fa=NULL;
while (T){
fa=T;
if (x<T->key)T=T->l;
else if(x>T->key)T=T->r;
else return ;//two the same keys
}
T=(Node*)malloc(sizeof(Node));
T->key=x;
T->l=T->r=NULL;
T->f=fa;
if (fa){
if (fa->key>x)fa->l=T;
else fa->r=T;
}
Splay(T);
}

void Delete(int x){
Node *T=Find(x);
if (NULL==T)return ;//error
rt=Join(T->l,T->r);
}

Node *Maxnum(Node *t){
Node *T=t;
while (T->r)T=T->r;
Splay(T);
return T;
}

Node *Minnum(Node *t){
Node *T=t;
while (T->l)T=T->l;
Splay(T);
return T;
}

Node *Last(int x){
Node *T=Find(x);
T=T->l;
return (Maxnum(T));
}

Node *Next(int x){
Node *T=Find(x);
T=T->r;
return (Minnum(T));
}

Node *Join(Node *t1,Node *t2){
if (NULL==t1)return t2;
if (NULL==t2)return t1;
Node *T=Maxnum(t1);
T->l=t2;
return T;
}

void Split(int x,Node *&t1,Node *&t2){
Node *T=Find(x);
t1=T->l;
t2=T->r;
}

void Inorder(Node *T){
if (NULL==T)return ;
Inorder(T->l);
printf("%d->",T->key);
Inorder(T->r);
}

void _Delete(){Delete(rt);}
void Delete(Node *T){
if (NULL==T)return ;
Delete(T->l);
Delete(T->r);
free(T);
}

private:
Node *rt;//root
};

int main(){
return 0;
}

[HNOI2002]营业额统计codevs1296
本题不用动脑子

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
/*
Author : cww97
Problem: p1296 营业额统计 CodeVs
*/
#include<cstdio>
#include<algorithm>
using namespace std;
const int INF=0xfffffff;
int ans;
struct Node{
int key;
Node *l,*r,*f;//left,right,father
};

class SplayTree{
public:
void Init(){
rt=NULL;
int x;scanf("%d",&x);
ans=x;
Insert(x);
}
void Zag(Node *x){//left rotate
Node *y=x->f;//y is the father of x
y->r = x->l;
if (x->l)x->l->f = y;//if x has left child
x->f =y->f;
if (y->f){//y is not root
if (y==y->f->l)y->f->l=x;//y if left child
else y->f->r=x;//y is right child
}
y->f=x;
x->l=y;
}
void Zig(Node *x){//right rotate
Node *y=x->f;//y is the father of x
y->l = x->r;
if (x->r)x->r->f=y;
x->f = y->f;
if (y->f){
if (y==y->f->l)y->f->l=x;
else y->f->r=x;
}
y->f=x;
x->r=y;
}
void Splay(Node *x){
while (x->f){
Node *p=x->f;
if (!p->f){
if (x==p->l)Zig(x);
else Zag(x);
}else if (x==p->l){
if (p==p->f->l){Zig(p);Zig(x);}
else {Zig(x);Zag(x);}
}else {//x==p->r
if (p==p->f->r){Zag(p);Zag(x);}
else {Zag(x);Zig(x);}
}
}
rt=x;
}

Node *Find(int x,int &d){
Node *T=rt;
while (T){
if (T->key==x){Splay(T);d=0;return T;}
else if (x < T->key){d=min(d,T->key-x);T=T->l;}
else {d=min(d,x-T->key);T=T->r;}
}
return T;
}
void Insert(int x){
Node *T=rt,*fa=NULL;
while (T){
fa=T;
if (x<T->key)T=T->l;
else if(x>T->key)T=T->r;
else return ;//two the same keys
}
T=(Node*)malloc(sizeof(Node));
T->key=x;
T->l=T->r=NULL;
T->f=fa;
if (fa){
if (fa->key>x)fa->l=T;
else fa->r=T;
}
Splay(T);
}

void Work(int x){
int d=INF;
Node *T=Find(x,d);
if (T)return;
ans+=d;
Insert(x);
}

void _Delete(){Delete(rt);}
void Delete(Node *T){
if (NULL==T)return ;
Delete(T->l);
Delete(T->r);
free(T);
}

private:
Node *rt;//root
};

int main(){
int n,x;scanf("%d",&n);
SplayTree T;
T.Init();
for (n--;n--;){
scanf("%d",&x);
T.Work(x);
}
printf("%d\n",ans);
T._Delete();
return 0;
}

[NOI2004]郁闷的的出纳员codevs1286
这题大致是多维护个size域来算第k大值,
写的好郁闷,,,下面的代码,,还是WA的状态,,
好烦好烦,暑假回头看看吧

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
#include<cstdio>
#include<algorithm>
using namespace std;
const int INF=0x7ffffff;
int m,d,ans;
struct Node{
int key,s;//size
Node *l,*r,*f;//left,right,father
};

class SplayTree{
public:
void Init(){rt=NULL;}
int S(Node *T){return (NULL==T)?0:T->s;}
void Zag(Node *x){//left rotate
Node *y=x->f;//y is the father of x
y->r = x->l;
if (x->l)x->l->f = y;//if x has left child
x->f =y->f;
if (y->f){//y is not root
if (y==y->f->l)y->f->l=x;//y if left child
else y->f->r=x;//y is right child
}
y->f=x;
x->l=y;
y->s=S(y->l)+S(y->r)+1;
x->s=S(x->l)+S(x->r)+1;
}
void Zig(Node *x){//right rotate
Node *y=x->f;//y is the father of x
y->l = x->r;
if (x->r)x->r->f=y;
x->f = y->f;
if (y->f){
if (y==y->f->l)y->f->l=x;
else y->f->r=x;
}
y->f=x;
x->r=y;
y->s=S(y->l)+S(y->r)+1;
x->s=S(x->l)+S(x->r)+1;
}
void Splay(Node *x){
while (x->f){
Node *p=x->f;
if (!p->f){
if (x==p->l)Zig(x);
else Zag(x);
}else if (x==p->l){
if (p==p->f->l){Zig(p);Zig(x);}
else {Zig(x);Zag(x);}
}else {//x==p->r
if (p==p->f->r){Zag(p);Zag(x);}
else {Zag(x);Zig(x);}
}
}
rt=x;
}

int Findkth(Node *T,int k){//find the K-th biggest number
//printf("T=%d,??l%d\n",T->key,S(T->r));
if (k<=S(T->r))return Findkth(T->r,k);
if (k==S(T->r)+1)return T->key;
return Findkth(T->l,k-S(T->r)-1);
}

void Insert(int x){
Node *T=rt,*fa=NULL;
while (T){
fa=T;
T->s++;
if (x<T->key)T=T->l;
else {T=T->r;}
}
T=(Node*)malloc(sizeof(Node));
T->key=x;
T->l=T->r=NULL;
T->f=fa;
T->s=1;
if (fa){
if (fa->key>x)fa->l=T;
else fa->r=T;
}
Splay(T);
}

int Goaway(Node *&T,Node *fa){
if (NULL==T)return 0;
int go;
if (T->key+d<m){
go=Goaway(T->r,T)+S(T->l)+1;
//printf("go=%d\n",go);
if (T==rt&&NULL==T->r){rt=NULL;return go;}
//else fa->l=NULL;
//Delete(T);
if (T->r){
T->r->s=T->s-go;
T=T->r;T->f=fa;
}
}else{
go=Goaway(T->l,T);
T->s-=go;
}
return go;
}

void Work(char ch,int x){
//printf("%c %d\n",ch,x);
if (ch=='I'&&x>=m)Insert(x-d);
if (ch=='A')d+=x;
if (ch=='S'){d-=x;ans+=Goaway(rt,NULL);}
if (ch=='F'){
if (S(rt) < x)puts("-1");
else printf("%d\n",Findkth(rt,x)+d);
}
//Inorder(rt);printf("d=%d,ans=%d\n",d,ans);
}

void Inorder(Node *T){
if (NULL==T)return ;
Inorder(T->l);
if (rt==T)printf("!");
printf("%d(%d)->",T->key,T->s);
Inorder(T->r);
}

void _Delete(){Delete(rt);}
void Delete(Node *T){
if (NULL==T)return ;
Delete(T->l);
Delete(T->r);
free(T);
}

private:
Node *rt;//root
};

int main(){
freopen("fuck.in","r",stdin);
SplayTree T;
T.Init();
int n,x;
char ch;
scanf("%d%d\n",&n,&m);
for (;n--;){
scanf("%c %d\n",&ch,&x);
T.Work(ch,x);
}
printf("%d\n",ans);
return 0;
}