模板

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
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn = 1000005;
const double _alpha = 0.8;
struct node{
node* ch[2];
int key,sz,cvr; bool ext;
node(int t1=0,node* son=NULL){
key = t1; sz = cvr = 1; ext = true; ch[0] = ch[1] = son;
}
void maintain(){
sz = ch[0]->sz + ch[1]->sz + ext;
cvr = ch[0]->cvr + ch[1]->cvr + 1;
}
bool isBad(){
return (ch[0]->cvr > cvr * _alpha + 5 )||(ch[1]->cvr > cvr * _alpha + 5);
}
} _poor[maxn],*p_top = _poor,nil,*null = &nil,*root,*bc[maxn];
int bc_top = 0;
typedef node* P_node;
P_node newnode(int key){
P_node p = bc_top ? bc[bc_top--] : p_top++;
*p=node(key,null); return p;
}
void Travel(P_node p,vector<P_node> &V){
if(p == null) return;
Travel(p->ch[0],V);
if(p->ext) V.push_back(p); else bc[++bc_top] = p;
Travel(p->ch[1],V);
}
P_node Build(vector<P_node> &V,int L,int R){
if(L > R) return null;
int mid = (L + R) >> 1; P_node p = V[mid];
p->ch[0] = Build(V,L,mid-1); p->ch[1] = Build(V,mid+1,R);
p->maintain(); return p;
}
P_node Rebuild(P_node &p){
static vector<P_node> V; V.clear();
Travel(p,V); p = Build(V,0,(int)V.size()-1);
}
P_node* _Insert(P_node &p,int val){
if(p == null){ p = newnode(val); return &null; }
p->sz++; p->cvr++;
P_node* res = _Insert(p->ch[val >= p->key],val);
if(p->isBad()) res = &p;
return res;
}
void _Erase(P_node p,int id){
p->sz--;
int t = p->ch[0]->sz + p->ext;
if(p->ext && id == t){ return p->ext = false; return; }
if(id <= t) _Erase(p->ch[0],id); else _Erase(p->ch[1],id - t);
}
void T_init(){
p_top = _poor;
null->ch[0] = null->ch[1] = null;
null->cvr = null->sz = null->key = 0;
root = null; bc_top = 0;
}
void Insert(int val){
P_node* p = _Insert(root,val);
if(*p != null) Rebuild(*p);
}
int Rank(int val){
P_node now = root; int ans = 1;
while(now != null){
if(now->key >= val) now = now->ch[0]; else{
ans += now->ch[0]->sz + now->ext;
now = now->ch[1];
}
}
return ans;
}
int Kth(int k){
P_node now = root;
while(now != null){
if(now->ch[0]->sz + 1 == k && now->ext) return now->key;
else if(now->ch[0]->sz >= k) now = now->ch[0];
else k-= now->ch[0]->sz + now->ext, now = now->ch[1];
}
}
void Erase_val(int k){
_Erase(root,Rank(k));
if(root->sz < _alpha * root->cvr) Rebuild(root);
}
void Erase_kth(int k){
_Erase(root,k);
if(root->sz < _alpha * root->cvr) Rebuild(root);
}
int n;
int main(){
freopen("scapegoat.in","r",stdin);
freopen("scapegoat.out","w",stdout);
scanf("%d",&n);
return 0;
}