【NOI2004】郁闷的出纳员Splay版

Posted by Cww97 on 2016-05-30

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/51538805
题目连接codevs1286
BZOJ1503,这里数据似乎强大一点,SlowSplay会TLE

学了Splay,,,练练手
多维护一个size域,就可以求k大值辣
昨晚调到接近3点还是RTE/WA,,cry
今天把每个节点加个cnt域就过了
(出现重复的数字的情况

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
#include<cstdio>
#include<algorithm>
using namespace std;
int m,d,ans;
struct Node{
int key,s,cnt;//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)+y->cnt;
x->s=S(x->l)+S(x->r)+x->cnt;
}
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)+y->cnt;
x->s=S(x->l)+S(x->r)+x->cnt;
}
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;
}

void Insert(int x){
Node *T=rt,*fa=NULL;
while (T){
fa=T;
T->s++;
if (x==T->key){T->cnt++;Splay(T);return;}
else 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=T->cnt=1;
if (fa){
if (fa->key>x)fa->l=T;
else fa->r=T;
}
Splay(T);
}

int Findkth(Node *T,int k){//find the K-th biggest number
if (k< S(T->r)+1)return Findkth(T->r,k);
else if (k>S(T->r)+T->cnt)Findkth(T->l,k-S(T->r)-T->cnt);
else {Splay(T);return T->key;}
}
void Goaway(Node *&T,Node *fa){
if (NULL==T)return ;
if (T->key>=m-d){Goaway(T->l,T);}
else {
ans+=S(T->l)+T->cnt;
T=T->r;
if (T)T->f=fa;
if (fa==NULL)rt=T;
Goaway(T,fa);
}
if (T)T->s=T->cnt+S(T->l)+S(T->r);
}

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

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;
}
这里写图片描述
这里写图片描述