「BZOJ-1056」「BZOJ-1862」-排名系统-Splay+map/SBT+HashSet

排名系统通常要应付三种请求:上传一条新的得分记录、查询某个玩家的当前排名以及返回某个区段内的排名记录。当某个玩家上传自己最新的得分记录时,他原有的得分记录会被删除。为了减轻服务器负担,在返回某个区段内的排名记录时,最多返回$10$ 条记录。

链接

bzoj1056

bzoj1862

题解

裸的平衡树套 $map$ 或平衡树套 $HashSet$,这里贴两份代码,Splay + map和SBT + HashSet

注意:第一份BZOJ神奇RE,SuperOj AC,第二份SuperOj数据把SBT卡退化了,光荣TLE,BZOJ AC

代码

Splay + map

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
#include <bits/stdc++.h>
const int MAXM = 2500000;
template<class T, size_t size>
struct MemoryPool {
T buf[size], *tail, *end;
inline T *alloc() {
if (top) return st[--top];
if (tail != end) return tail++;
return new T;
}
MemoryPool() : tail(buf), end(buf + size), top(0) {}
int top;
T *st[size];
inline void recycle(T *x) {
if (top > size) delete x;
else st[top++] = x;
}
};
struct Splay {
struct Node {
Node *c[2], *fa, **root;
std::map<std::string, Node *>::iterator it;
std::pair<int, int> x;
int size;
inline Node *init(Node **root, Node *fa, const std::pair<int, int> &x, const std::map<std::string, Node *>::iterator it) { return this->fa = fa, this->root = root, this->it = it, this->x = x, this->size = 0, c[0] = c[1] = NULL, this; }
inline void recycle(MemoryPool<Node, MAXM> &pool) {
if (c[0]) c[0]->recycle(pool), pool.recycle(c[0]), c[0] = NULL;
if (c[1]) c[1]->recycle(pool), pool.recycle(c[1]), c[1] = NULL;
}
inline void maintain() { size = (c[0] ? c[0]->size : 0) + (c[1] ? c[1]->size : 0) + 1; }
inline int relation() { return this == fa->c[1]; }
inline void rotate() {
Node *o = fa;
register int x = relation();
if (o->fa) o->fa->c[o->relation()] = this;
fa = o->fa, o->c[x] = c[x ^ 1];
if (c[x ^ 1]) c[x ^ 1]->fa = o;
c[x ^ 1] = o, o->fa = this, o->maintain(), maintain();
if (!fa) *root = this;
}
inline Node *splay(Node *t = NULL) {
while (fa != t) {
if (fa->fa == t) rotate();
else if (relation() == fa->relation()) fa->rotate(), rotate();
else rotate(), rotate();
}
return this;
}
inline Node *pre() {
Node *v = splay()->c[0];
while (v->c[1]) v = v->c[1];
return v;
}
inline Node *suc() {
Node *v = splay()->c[1];
while (v->c[0]) v = v->c[0];
return v;
}
inline int rank() { return c[0] ? c[0]->size : 0; }
} *root;
MemoryPool<Node, MAXM> pool;
Splay(const std::map<std::string, Node *>::iterator null) : root(NULL) { insert(std::make_pair(INT_MIN, INT_MIN), null), insert(std::make_pair(INT_MAX, INT_MAX), null); }
inline Node *insert(const std::pair<int, int> &x, std::map<std::string, Node *>::iterator it) {
Node **v = &root, *fa = NULL;
while (*v) fa = *v, fa->size++, v = &fa->c[x > fa->x];
return *v = pool.alloc()->init(&root, fa, x, it), (*v)->splay();
}
inline void erase(Node *v) {
Node *l = v->pre(), *r = v->suc();
r->splay(), l->splay(r);
v->recycle(pool), pool.recycle(v), v = NULL, l->c[1] = NULL, l->size--, r->size--;
}
inline Node *select(int k) {
register int x = k;
Node *v = root;
while (v->rank() != x) {
if (v->rank() > x) v = v->c[0];
else x -= v->rank() + 1, v = v->c[1];
}
return v->splay();
}
inline Node *select(int l, int r) {
Node *pre = select(l - 1), *suc = select(r + 1);
return suc->splay(), pre->splay(suc)->c[1];
}
inline int size() { return root->size - 2; }
};
std::map<std::string, Splay::Node *> map;
Splay splay(map.end());
inline void dfs(Splay::Node *v, std::vector<const std::string *> &vec) {
if (!v) return;
dfs(v->c[0], vec);
if (v->it != map.end()) vec.push_back(&v->it->first);
dfs(v->c[1], vec);
}
inline int parseInt(const std::string &s) {
register int x = 0;
for (std::string::const_iterator it = s.begin(); it != s.end(); it++) x = (x << 1) + (x << 3) + ((*it) ^ '0');
return x;
}
int main() {
std::ios::sync_with_stdio(0);
std::cin.tie(0);
register int n;
std::cin >> n;
while (n--) {
std::string cmd;
std::cin >> cmd;
if (cmd[0] == '+') {
std::string name = cmd.substr(1, cmd.length() - 1);
register int x;
std::cin >> x;
std::map<std::string, Splay::Node *>::iterator it = map.find(name);
if (it != map.end()) splay.erase(it->second);
else it = map.insert(std::make_pair(name, static_cast<Splay::Node *>(NULL))).first;
it->second = splay.insert(std::make_pair(-x, -n), it);
} else if (cmd[0] == '?') {
std::string arg = cmd.substr(1, cmd.length() - 1);
if (arg[0] >= '0' && arg[0] <= '9') {
register int x = parseInt(arg);
Splay::Node *v = splay.select(x, std::min(splay.size(), x + 10 - 1));
std::vector<const std::string *> vec;
dfs(v, vec);
for (std::vector<const std::string *>::iterator it = vec.begin(); it != vec.end(); it++) std::cout << **it << (it == vec.end() - 1 ? '\n' : ' ');
} else {
Splay::Node *v = map[arg];
std::cout << v->splay()->rank() << '\n';
}
}
}
return 0;
}

SBT + HashSet

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
#include <bits/stdc++.h>
using std::min;
using std::pair;
using std::string;
typedef unsigned long long ull;
const int MAXN = 260000;
struct SizeBalanceTree {
struct Node {
int v, s, t, id;
Node *ch[2];
inline void init(int _v = 0, int _s = 0, int _t = 0, int _id = 0, Node *p = NULL) { ch[0] = ch[1] = p, v = _v, s = _s, t = _t, id = _id; }
inline void pushUp() { s = ch[0]->s + ch[1]->s + 1; }
inline int cmp(int _v, int _t) const { if (v == _v) return t == _t ? -1 : _t > t; return v > _v; }
};
Node stack[MAXN];
Node *root, *null, *tail;
Node *store[MAXN];
int top;
inline void init() { tail = &stack[0], null = tail++, null->init(), root = null, top = 0; }
inline Node *newNode(int v, int t, int id) {
Node *p = null;
if (top) p = store[--top];
else p = tail++;
p->init(v, 1, t, id, null);
return p;
}
inline void rotate(Node* &x, int d) {
Node *k = x->ch[!d];
x->ch[!d] = k->ch[d], k->ch[d] = x, k->s = x->s, x->pushUp(), x = k;
}
inline void maintain(Node* &x, int d) {
if (x->ch[d] == null) return;
if (x->ch[d]->ch[d]->s > x->ch[!d]->s) rotate(x, !d);
else if (x->ch[d]->ch[!d]->s > x->ch[!d]->s) rotate(x->ch[d], d), rotate(x, !d);
else return;
maintain(x, 0), maintain(x, 1);
}
inline void insert(Node* &x, int v, int t, int id) {
if (x == null) {
x = newNode(v, t, id);
return;
} else {
x->s++;
int d = x->cmp(v, t);
insert(x->ch[d], v, t, id), x->pushUp(), maintain(x, d);
}
}
inline void erase(Node* &x, int v, int t) {
if (x == null) return;
x->s--;
int d = x->cmp(v, t);
if (-1 == d) {
if (!x->ch[0]->s || !x->ch[1]->s) {
store[top++] = x, x = x->ch[0]->s ? x->ch[0] : x->ch[1];
} else {
Node *ret = x->ch[1];
for (; ret->ch[0] != null; ret = ret->ch[0]);
x->v = ret->v, x->t = ret->t, x->id = ret->id;
erase(x->ch[1], ret->v, ret->t);
}
} else {
erase(x->ch[d], v, t);
}
if (x != null) x->pushUp();
}
inline int select(Node *x, int v, int t) {
int k = 0, cur = 0;
for (; x != null;) {
int d = x->cmp(v, t);
k = x->ch[0]->s;
if (-1 == d) break;
else if (!d) x = x->ch[0];
else cur += k + 1, x = x->ch[1];
}
return cur + k + 1;
}
inline int rank(Node *x, int k) {
for (; x != null;) {
int t = x->ch[0]->s;
if (k == t + 1) break;
else if (k <= t) x = x->ch[0];
else k -= t + 1, x = x->ch[1];
}
return x->id;
}
inline void insert(int v, int t, int id) { insert(root, v, t, id); }
inline void erase(int v, int t) { erase(root, v, t); }
inline int select(int v, int t) { return select(root, v, t); }
inline int rank(int k) { return rank(root, k); }
} sbt;
#define BASE 133
#define MOD 299997
#define MAXN 500000
int now[MAXN], _time[MAXN];
struct HashSet {
int head[MAXN];
int tot, next[MAXN];
ull hash[MAXN];
char src[MAXN][12];
inline ull getHash(char *s) {
ull ret = 0;
while (*s != '\0') ret = ret * BASE + *s++;
return ret;
}
inline int insert(char *s) {
ull _hash = getHash(s);
int x = _hash % MOD;
for (int i = head[x]; i; i = next[i]) if (hash[i] == _hash) return i;
next[++tot] = head[x], hash[tot] = _hash, head[x] = tot;
strcpy(src[tot], s);
return tot;
}
} map;
int main() {
int n, v;
sbt.init();
char s1[100], buf[100];
scanf("%d\n", &n);
for (int i = 1; i <= n; i++) {
gets(buf);
if (buf[0] == '+') {
sscanf(&buf[1], "%s %d", s1, &v);
int x = map.insert(s1);
if (now[x]) sbt.erase(now[x], _time[x]);
now[x] = v, _time[x] = i;
sbt.insert(now[x], _time[x], x);
} else if (buf[0] == '?' && isalpha(buf[1])) {
sscanf(&buf[1], "%s", s1);
int x = map.insert(s1);
printf("%d\n", sbt.select(now[x], _time[x]));
} else {
int ed;
sscanf(&buf[1], "%d", &v);
ed = min(v + 9, map.tot);
for (int j = v; j <= ed; j++) {
printf("%s%c", map.src[sbt.rank(j)], j != ed ? ' ' : '\n');
}
}
}
return 0;
}
分享到