原题链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1862
很恶心的 一道题，我也不晓得自己是第几次写这题了%>_<%。
写了两种方法，平衡树+哈希和平衡树+map。哈希函数是抄别人的。比较了一下还是哈希快一些。
题意很简单，就不说了。
具体思路是，平衡树维护排名，map建立姓名和分数一一对应的关系。
求rank时题意默认是越先提交得分排名越靠前(相同得分的条件下)。
具体如下：
平衡树+map
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<map>
using std::min;
using std::map;
using std::string;
const int Max_N = ;
char src[Max_N][];
typedef char State[];
struct Node{
int v, s, t, id;
Node *ch[];
inline void set(int _v = , int _s = , int _t = , int _id = , Node *p = NULL){
ch[] = ch[] = p;
v = _v, s = _s, t = _t, id = _id;
}
inline void push_up(){
s = ch[]->s + ch[]->s + ;
}
inline int cmp(int _v, int _t) const{
if (v == _v){
return t == _t ? - : _t > t;
}
return v > _v;
}
};
struct SizeBalanceTree{
Node stack[Max_N];
Node *root, *null, *tail;
Node *store[Max_N];
int top;
void init(){
tail = &stack[];
null = tail++;
null->set();
root = null;
top = ;
}
inline Node *newNode(int v, int t, int id){
Node *p = null;
if (top) p = store[--top];
else p = tail++;
p->set(v, , 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->push_up();
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, ), Maintain(x, );
}
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->push_up();
Maintain(x, d);
}
}
inline void del(Node* &x, int v, int t){
if (x == null) return;
x->s--;
int d = x->cmp(v, t);
if (- == d){
if (!x->ch[]->s || !x->ch[]->s){
store[top++] = x;
x = x->ch[]->s ? x->ch[] : x->ch[];
} else {
Node *ret = x->ch[];
for (; ret->ch[] != null; ret = ret->ch[]);
x->v = ret->v, x->t = ret->t, x->id = ret->id;
del(x->ch[], ret->v, ret->t);
}
} else {
del(x->ch[d], v, t);
}
if (x != null) x->push_up();
}
inline int find(Node *x, int v, int t){
int k = , cur = ;
for (; x != null;){
int d = x->cmp(v, t);
k = x->ch[]->s;
if (- == d) break;
else if (!d) x = x->ch[];
else cur += k + , x = x->ch[];
}
return cur + k + ;
}
inline int rank(Node *x, int k){
for (; x != null;){
int t = x->ch[]->s;
if (k == t + ) break;
else if (k <= t) x = x->ch[];
else k -= t + , x = x->ch[];
}
return x->id;
}
inline void insert(int v, int t, int id){
insert(root, v, t, id);
}
inline void del(int v, int t){
del(root, v, t);
}
inline int find(int v, int t){
return find(root, v, t);
}
inline int rank(int k){
return rank(root, k);
}
}sbt;
struct node{
int v, t, id;
node(){};
node(int _v, int _t, int _id) :v(_v), t(_t), id(_id){}
};
map<string, node > stri;
void gogo(char *s, int v, int t, int &tot){
string str(s);
if (stri.count(str) != ){
sbt.del(stri[str].v, stri[str].t);
stri[str].v = v, stri[str].t = t;
sbt.insert(v, t, stri[str].id);
return;
}
strcpy(src[++tot], s);
sbt.insert(v, t, tot);
node ret(v, t, tot);
stri[str] = ret;
}
int main(){
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w+", stdout);
#endif
sbt.init();
State s1, buf;
int n, v, tot = ;
scanf("%d\n", &n);
for (int i = ; i <= n; i++){
gets(buf);
if (buf[] == '+'){
sscanf(&buf[], "%s %d", s1, &v);
gogo(s1, v, i, tot);
} else if (buf[] == '?' && isalpha(buf[])){
sscanf(&buf[], "%s", s1);
printf("%d\n", sbt.find(stri[s1].v, stri[s1].t));
} else {
int ed;
sscanf(&buf[], "%d", &v);
ed = min(v + , tot);
for (int j = v; j <= ed; j++) {
printf("%s%c", src[sbt.rank(j)], j != ed ? ' ' : '\n');
}
}
}
return ;
}
平衡树+哈希
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<map>
using std::min;
using std::pair;
using std::string;
typedef char State[];
typedef unsigned long long ull;
const int Max_N = ;
struct Node{
int v, s, t, id;
Node *ch[];
inline void
set(int _v = , int _s = , int _t = , int _id = , Node *p = NULL){
ch[] = ch[] = p;
v = _v, s = _s, t = _t, id = _id;
}
inline void push_up(){
s = ch[]->s + ch[]->s + ;
}
inline int cmp(int _v, int _t) const{
if (v == _v){
return t == _t ? - : _t > t;
}
return v > _v;
}
};
struct SizeBalanceTree{
Node stack[Max_N];
Node *root, *null, *tail;
Node *store[Max_N];
int top;
void init(){
tail = &stack[];
null = tail++;
null->set();
root = null;
top = ;
}
inline Node *newNode(int v, int t, int id){
Node *p = null;
if (top) p = store[--top];
else p = tail++;
p->set(v, , 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->push_up();
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, ), Maintain(x, );
}
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->push_up();
Maintain(x, d);
}
}
inline void del(Node* &x, int v, int t){
if (x == null) return;
x->s--;
int d = x->cmp(v, t);
if (- == d){
if (!x->ch[]->s || !x->ch[]->s){
store[top++] = x;
x = x->ch[]->s ? x->ch[] : x->ch[];
} else {
Node *ret = x->ch[];
for (; ret->ch[] != null; ret = ret->ch[]);
x->v = ret->v, x->t = ret->t, x->id = ret->id;
del(x->ch[], ret->v, ret->t);
}
} else {
del(x->ch[d], v, t);
}
if (x != null) x->push_up();
}
inline int find(Node *x, int v, int t){
int k = , cur = ;
for (; x != null;){
int d = x->cmp(v, t);
k = x->ch[]->s;
if (- == d) break;
else if (!d) x = x->ch[];
else cur += k + , x = x->ch[];
}
return cur + k + ;
}
inline int rank(Node *x, int k){
for (; x != null;){
int t = x->ch[]->s;
if (k == t + ) break;
else if (k <= t) x = x->ch[];
else k -= t + , x = x->ch[];
}
return x->id;
}
inline void insert(int v, int t, int id){
insert(root, v, t, id);
}
inline void del(int v, int t){
del(root, v, t);
}
inline int find(int v, int t){
return find(root, v, t);
}
inline int rank(int k){
return rank(root, k);
}
}sbt;
#define BASE 133
#define MOD 299997
#define MAXN 500000
int now[Max_N], _time[Max_N];
struct HashSet{
int head[MAXN];
int tot, next[MAXN];
ull hash[MAXN];
char src[Max_N][];
inline ull GetHash(char *s){
ull re = ;
while (*s != '\0') re = re * BASE + *s++;
return re;
}
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(){
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w+", stdout);
#endif
int n, v;
sbt.init();
State s1, buf;
scanf("%d\n", &n);
for (int i = ; i <= n; i++){
gets(buf);
if (buf[] == '+'){
sscanf(&buf[], "%s %d", s1, &v);
int x = map.Insert(s1);
if (now[x]) sbt.del(now[x], _time[x]);
now[x] = v, _time[x] = i;
sbt.insert(now[x], _time[x], x);
} else if (buf[] == '?' && isalpha(buf[])){
sscanf(&buf[], "%s", s1);
int x = map.Insert(s1);
printf("%d\n", sbt.find(now[x], _time[x]));
} else {
int ed;
sscanf(&buf[], "%d", &v);
ed = min(v + , map.tot);
for (int j = v; j <= ed; j++) {
printf("%s%c", map.src[sbt.rank(j)], j != ed ? ' ' : '\n');
}
}
}
return ;
}