hdu 4585 Shaolin，hdu4585shaolin
原題鏈接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=46093
![]()
1 #include<cstdio>
2 #include<cstdlib>
3 #include<iostream>
4 #include<algorithm>
5 const int Max_N = 101000;
6 const int INF = 0x7fffffff;
7 struct Node{
8 int v, id, s;
9 Node *ch[2];
10 inline void
11 set(int _v = 0, int _id = 0, int _s = 0, Node *p = NULL){
12 ch[0] = ch[1] = p;
13 v = _v, id = _id, s = _s;
14 }
15 inline void push_up(){
16 s = ch[0]->s + ch[1]->s + 1;
17 }
18 inline int cmp(int x) const{
19 return x > v;
20 }
21 };
22 struct SizeBalanceTree{
23 Node *tail, *root, *null;
24 Node stack[Max_N];
25 void init(){
26 tail = &stack[0];
27 null = tail++;
28 null->set();
29 root = null;
30 }
31 inline Node *newNode(int v, int id){
32 Node *p = tail++;
33 p->set(v, id, 1, null);
34 return p;
35 }
36 inline void rotate(Node* &x, int d){
37 Node *k = x->ch[!d];
38 x->ch[!d] = k->ch[d];
39 k->ch[d] = x;
40 k->s = x->s;
41 x->push_up();
42 x = k;
43 }
44 inline void Maintain(Node* &x, int d){
45 if (x->ch[d] == null) return;
46 if (x->ch[d]->ch[d]->s > x->ch[!d]->s){
47 rotate(x, !d);
48 } else if (x->ch[d]->ch[!d]->s > x->ch[!d]->s){
49 rotate(x->ch[d], d), rotate(x, !d);
50 } else {
51 return;
52 }
53 Maintain(x, 0), Maintain(x, 1);
54 }
55 inline void insert(Node* &x, int v, int id){
56 if (x == null){
57 x = newNode(v, id);
58 return;
59 } else {
60 x->s++;
61 int d = x->cmp(v);
62 insert(x->ch[d], v, id);
63 x->push_up();
64 Maintain(x, d);
65 }
66 }
67 inline void insert(int v, int id){
68 insert(root, v, id);
69 }
70 inline Node *select(Node *x, int v, int dx){
71 Node *pre = null;
72 while (x != null && x->v != v){
73 int d = x->cmp(v);
74 if (d == !dx) pre = x;
75 x = x->ch[d];
76 }
77 x = x->ch[dx];
78 if (x == null){
79 return pre;
80 } else {
81 while (x->ch[!dx] != null) x = x->ch[!dx];
82 return x;
83 }
84 }
85 inline int calc(Node *r, int k) {
86 if (r == null) return INF;
87 return std::abs(r->v - k);
88 }
89 inline void gogo(int id, int v){
90 int ans = 0;
91 Node *k1 = select(root, v, 0);
92 Node *k2 = select(root, v, 1);
93 int d1 = calc(k1, v), d2 = calc(k2, v);
94 ans = d1 > d2 ? k2->id : k1->id;
95 printf("%d %d\n", id, ans);
96 }
97 }sbt;
98 int main(){
99 #ifdef LOCAL
100 freopen("in.txt", "r", stdin);
101 freopen("out.txt", "w+", stdout);
102 #endif
103 int n, id, v;
104 while (~scanf("%d", &n) && n){
105 sbt.init();
106 sbt.insert((int)1e9, 1);
107 for (int i = 0; i < n; i++){
108 scanf("%d %d", &id, &v);
109 sbt.insert(v, id);
110 sbt.gogo(id, v);
111 }
112 }
113 return 0;
114 }
View Code
