bzoj 1862/1056 [HAOI2008]排名系統，bzojhaoi2008
原題鏈接：http://www.lydsy.com/JudgeOnline/problem.php?id=1862
很惡心的 一道題，我也不曉得自己是第幾次寫這題了%>_<%。
寫了兩種方法，平衡樹+哈希和平衡樹+map。哈希函數是抄別人的。比較了一下還是哈希快一些。
題意很簡單，就不說了。
具體思路是，平衡樹維護排名，map建立姓名和分數一一對應的關系。
求rank時題意默認是越先提交得分排名越靠前(相同得分的條件下)。
具體如下：
平衡樹+map
![]()
1 #include<algorithm>
2 #include<iostream>
3 #include<cstdlib>
4 #include<cstring>
5 #include<cstdio>
6 #include<string>
7 #include<map>
8 using std::min;
9 using std::map;
10 using std::string;
11 const int Max_N = 260000;
12 char src[Max_N][12];
13 typedef char State[100];
14 struct Node{
15 int v, s, t, id;
16 Node *ch[2];
17 inline void set(int _v = 0, int _s = 0, int _t = 0, int _id = 0, Node *p = NULL){
18 ch[0] = ch[1] = p;
19 v = _v, s = _s, t = _t, id = _id;
20 }
21 inline void push_up(){
22 s = ch[0]->s + ch[1]->s + 1;
23 }
24 inline int cmp(int _v, int _t) const{
25 if (v == _v){
26 return t == _t ? -1 : _t > t;
27 }
28 return v > _v;
29 }
30 };
31 struct SizeBalanceTree{
32 Node stack[Max_N];
33 Node *root, *null, *tail;
34 Node *store[Max_N];
35 int top;
36 void init(){
37 tail = &stack[0];
38 null = tail++;
39 null->set();
40 root = null;
41 top = 0;
42 }
43 inline Node *newNode(int v, int t, int id){
44 Node *p = null;
45 if (top) p = store[--top];
46 else p = tail++;
47 p->set(v, 1, t, id, null);
48 return p;
49 }
50 inline void rotate(Node* &x, int d){
51 Node *k = x->ch[!d];
52 x->ch[!d] = k->ch[d];
53 k->ch[d] = x;
54 k->s = x->s;
55 x->push_up();
56 x = k;
57 }
58 inline void Maintain(Node* &x, int d){
59 if (x->ch[d] == null) return;
60 if (x->ch[d]->ch[d]->s > x->ch[!d]->s){
61 rotate(x, !d);
62 } else if (x->ch[d]->ch[!d]->s > x->ch[!d]->s){
63 rotate(x->ch[d], d), rotate(x, !d);
64 } else {
65 return;
66 }
67 Maintain(x, 0), Maintain(x, 1);
68 }
69 inline void insert(Node* &x, int v, int t, int id){
70 if (x == null){
71 x = newNode(v, t, id);
72 return;
73 } else {
74 x->s++;
75 int d = x->cmp(v, t);
76 insert(x->ch[d], v, t, id);
77 x->push_up();
78 Maintain(x, d);
79 }
80 }
81 inline void del(Node* &x, int v, int t){
82 if (x == null) return;
83 x->s--;
84 int d = x->cmp(v, t);
85 if (-1 == d){
86 if (!x->ch[0]->s || !x->ch[1]->s){
87 store[top++] = x;
88 x = x->ch[0]->s ? x->ch[0] : x->ch[1];
89 } else {
90 Node *ret = x->ch[1];
91 for (; ret->ch[0] != null; ret = ret->ch[0]);
92 x->v = ret->v, x->t = ret->t, x->id = ret->id;
93 del(x->ch[1], ret->v, ret->t);
94 }
95 } else {
96 del(x->ch[d], v, t);
97 }
98 if (x != null) x->push_up();
99 }
100 inline int find(Node *x, int v, int t){
101 int k = 0, cur = 0;
102 for (; x != null;){
103 int d = x->cmp(v, t);
104 k = x->ch[0]->s;
105 if (-1 == d) break;
106 else if (!d) x = x->ch[0];
107 else cur += k + 1, x = x->ch[1];
108 }
109 return cur + k + 1;
110 }
111 inline int rank(Node *x, int k){
112 for (; x != null;){
113 int t = x->ch[0]->s;
114 if (k == t + 1) break;
115 else if (k <= t) x = x->ch[0];
116 else k -= t + 1, x = x->ch[1];
117 }
118 return x->id;
119 }
120 inline void insert(int v, int t, int id){
121 insert(root, v, t, id);
122 }
123 inline void del(int v, int t){
124 del(root, v, t);
125 }
126 inline int find(int v, int t){
127 return find(root, v, t);
128 }
129 inline int rank(int k){
130 return rank(root, k);
131 }
132 }sbt;
133 struct node{
134 int v, t, id;
135 node(){};
136 node(int _v, int _t, int _id) :v(_v), t(_t), id(_id){}
137 };
138 map<string, node > stri;
139 void gogo(char *s, int v, int t, int &tot){
140 string str(s);
141 if (stri.count(str) != 0){
142 sbt.del(stri[str].v, stri[str].t);
143 stri[str].v = v, stri[str].t = t;
144 sbt.insert(v, t, stri[str].id);
145 return;
146 }
147 strcpy(src[++tot], s);
148 sbt.insert(v, t, tot);
149 node ret(v, t, tot);
150 stri[str] = ret;
151 }
152 int main(){
153 #ifdef LOCAL
154 freopen("in.txt", "r", stdin);
155 freopen("out.txt", "w+", stdout);
156 #endif
157 sbt.init();
158 State s1, buf;
159 int n, v, tot = 0;
160 scanf("%d\n", &n);
161 for (int i = 1; i <= n; i++){
162 gets(buf);
163 if (buf[0] == '+'){
164 sscanf(&buf[1], "%s %d", s1, &v);
165 gogo(s1, v, i, tot);
166 } else if (buf[0] == '?' && isalpha(buf[1])){
167 sscanf(&buf[1], "%s", s1);
168 printf("%d\n", sbt.find(stri[s1].v, stri[s1].t));
169 } else {
170 int ed;
171 sscanf(&buf[1], "%d", &v);
172 ed = min(v + 9, tot);
173 for (int j = v; j <= ed; j++) {
174 printf("%s%c", src[sbt.rank(j)], j != ed ? ' ' : '\n');
175 }
176 }
177 }
178 return 0;
179 }
View Code
平衡樹+哈希
![]()
1 #include<algorithm>
2 #include<iostream>
3 #include<cstdlib>
4 #include<cstring>
5 #include<cstdio>
6 #include<string>
7 #include<map>
8 using std::min;
9 using std::pair;
10 using std::string;
11 typedef char State[100];
12 typedef unsigned long long ull;
13 const int Max_N = 260000;
14 struct Node{
15 int v, s, t, id;
16 Node *ch[2];
17 inline void
18 set(int _v = 0, int _s = 0, int _t = 0, int _id = 0, Node *p = NULL){
19 ch[0] = ch[1] = p;
20 v = _v, s = _s, t = _t, id = _id;
21 }
22 inline void push_up(){
23 s = ch[0]->s + ch[1]->s + 1;
24 }
25 inline int cmp(int _v, int _t) const{
26 if (v == _v){
27 return t == _t ? -1 : _t > t;
28 }
29 return v > _v;
30 }
31 };
32 struct SizeBalanceTree{
33 Node stack[Max_N];
34 Node *root, *null, *tail;
35 Node *store[Max_N];
36 int top;
37 void init(){
38 tail = &stack[0];
39 null = tail++;
40 null->set();
41 root = null;
42 top = 0;
43 }
44 inline Node *newNode(int v, int t, int id){
45 Node *p = null;
46 if (top) p = store[--top];
47 else p = tail++;
48 p->set(v, 1, t, id, null);
49 return p;
50 }
51 inline void rotate(Node* &x, int d){
52 Node *k = x->ch[!d];
53 x->ch[!d] = k->ch[d];
54 k->ch[d] = x;
55 k->s = x->s;
56 x->push_up();
57 x = k;
58 }
59 inline void Maintain(Node* &x, int d){
60 if (x->ch[d] == null) return;
61 if (x->ch[d]->ch[d]->s > x->ch[!d]->s){
62 rotate(x, !d);
63 } else if (x->ch[d]->ch[!d]->s > x->ch[!d]->s){
64 rotate(x->ch[d], d), rotate(x, !d);
65 } else {
66 return;
67 }
68 Maintain(x, 0), Maintain(x, 1);
69 }
70 inline void insert(Node* &x, int v, int t, int id){
71 if (x == null){
72 x = newNode(v, t, id);
73 return;
74 } else {
75 x->s++;
76 int d = x->cmp(v, t);
77 insert(x->ch[d], v, t, id);
78 x->push_up();
79 Maintain(x, d);
80 }
81 }
82 inline void del(Node* &x, int v, int t){
83 if (x == null) return;
84 x->s--;
85 int d = x->cmp(v, t);
86 if (-1 == d){
87 if (!x->ch[0]->s || !x->ch[1]->s){
88 store[top++] = x;
89 x = x->ch[0]->s ? x->ch[0] : x->ch[1];
90 } else {
91 Node *ret = x->ch[1];
92 for (; ret->ch[0] != null; ret = ret->ch[0]);
93 x->v = ret->v, x->t = ret->t, x->id = ret->id;
94 del(x->ch[1], ret->v, ret->t);
95 }
96 } else {
97 del(x->ch[d], v, t);
98 }
99 if (x != null) x->push_up();
100 }
101 inline int find(Node *x, int v, int t){
102 int k = 0, cur = 0;
103 for (; x != null;){
104 int d = x->cmp(v, t);
105 k = x->ch[0]->s;
106 if (-1 == d) break;
107 else if (!d) x = x->ch[0];
108 else cur += k + 1, x = x->ch[1];
109 }
110 return cur + k + 1;
111 }
112 inline int rank(Node *x, int k){
113 for (; x != null;){
114 int t = x->ch[0]->s;
115 if (k == t + 1) break;
116 else if (k <= t) x = x->ch[0];
117 else k -= t + 1, x = x->ch[1];
118 }
119 return x->id;
120 }
121 inline void insert(int v, int t, int id){
122 insert(root, v, t, id);
123 }
124 inline void del(int v, int t){
125 del(root, v, t);
126 }
127 inline int find(int v, int t){
128 return find(root, v, t);
129 }
130 inline int rank(int k){
131 return rank(root, k);
132 }
133 }sbt;
134 #define BASE 133
135 #define MOD 299997
136 #define MAXN 500000
137 int now[Max_N], _time[Max_N];
138 struct HashSet{
139 int head[MAXN];
140 int tot, next[MAXN];
141 ull hash[MAXN];
142 char src[Max_N][12];
143 inline ull GetHash(char *s){
144 ull re = 0;
145 while (*s != '\0') re = re * BASE + *s++;
146 return re;
147 }
148 inline int Insert(char *s) {
149 ull _hash = GetHash(s);
150 int x = _hash % MOD;
151 for (int i = head[x]; i; i = next[i]){
152 if (hash[i] == _hash) return i;
153 }
154 next[++tot] = head[x];
155 hash[tot] = _hash;
156 head[x] = tot;
157 strcpy(src[tot], s);
158 return tot;
159 }
160 }map;
161 int main(){
162 #ifdef LOCAL
163 freopen("in.txt", "r", stdin);
164 freopen("out.txt", "w+", stdout);
165 #endif
166 int n, v;
167 sbt.init();
168 State s1, buf;
169 scanf("%d\n", &n);
170 for (int i = 1; i <= n; i++){
171 gets(buf);
172 if (buf[0] == '+'){
173 sscanf(&buf[1], "%s %d", s1, &v);
174 int x = map.Insert(s1);
175 if (now[x]) sbt.del(now[x], _time[x]);
176 now[x] = v, _time[x] = i;
177 sbt.insert(now[x], _time[x], x);
178 } else if (buf[0] == '?' && isalpha(buf[1])){
179 sscanf(&buf[1], "%s", s1);
180 int x = map.Insert(s1);
181 printf("%d\n", sbt.find(now[x], _time[x]));
182 } else {
183 int ed;
184 sscanf(&buf[1], "%d", &v);
185 ed = min(v + 9, map.tot);
186 for (int j = v; j <= ed; j++) {
187 printf("%s%c", map.src[sbt.rank(j)], j != ed ? ' ' : '\n');
188 }
189 }
190 }
191 return 0;
192 }
View Code
