[BZOJ1056][BZOJ1862][HAOI2008][Zjoi2006]排名系统
试题描述
排名系统通常要应付三种请求：上传一条新的得分记录、查询某个玩家的当前排名以及返回某个区段内的排名记录。当某个玩家上传自己最新的得分记录时，他原有的得分记录会被删除。为了减轻服务器负担，在返回某个区段内的排名记录时，最多返回10条记录。
输入
第一行是一个整数n（n>=10）表示请求总数目。接下来n行,每行包含了一个请求。请求的具体格式如下： +Name Score 上传最新得分记录。Name表示玩家名字，由大写英文字母组成，不超过10个字符。Score为最多8位的正整数。 ?Name 查询玩家排名。该玩家的得分记录必定已经在前面上传。 ?Index 返回自第Index名开始的最多10名玩家名字。Index必定合法，即不小于1，也不大于当前有记录的玩家总数。
输出
对于?Name格式的请求，应输出一个整数表示该玩家当前的排名。对于?Index格式的请求，应在一行中依次输出从第Index名开始的最多10名玩家姓名，用一个空格分隔。
输入示例
+ADAM
+BOB
+TOM
+CATHY
?TOM
?
+DAM
+BOB
+ADAM
+FRANK
+LEO
+KAINE
+GRACE
+WALT
+SANDY
+MICK
+JACK
?
?
?KAINE
输出示例
CATHY TOM ADAM BOB
CATHY LEO WALT MICK KAINE GRACE SANDY JACK TOM BOB
MICK KAINE GRACE SANDY JACK TOM BOB ADAM DAM
数据规模及约定
N<=250000
题解
用颗 trie 维护一下每个串对应的信息，用 treap 维护排名等等乱七八糟的东西。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std; int read() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
return x * f;
} #define maxn 250010
#define maxa 26
int son[maxa][maxn], id[maxn], sc[maxn], qaq;
void insert(int j, char* s) {
int u = 0, l = strlen(s);
for(int i = 0; i < l; i++) {
if(!son[s[i]-'A'][u]) son[s[i]-'A'][u] = ++qaq;
u = son[s[i]-'A'][u];
}
id[u] = j;
return ;
}
int getid(char* s) {
int u = 0, l = strlen(s);
for(int i = 0; i < l; i++) {
if(!son[s[i]-'A'][u]) return 0;
u = son[s[i]-'A'][u];
}
return id[u];
} struct Node {
char name[15];
int v, r, siz;
Node() {}
Node(int _1, int _2, char* _3): v(_1), r(_2) {
memcpy(name, _3, sizeof(name));
}
bool operator < (Node t) {
return v != t.v ? v > t.v : getid(name) < getid(t.name);
}
bool operator == (Node t) const {
return v == t.v && !strcmp(name, t.name);
}
} ns[maxn];
int ToT, rt, fa[maxn], ch[2][maxn];
void maintain(int o) {
ns[o].siz = 1;
for(int i = 0; i < 2; i++) if(ch[i][o])
ns[o].siz += ns[ch[i][o]].siz;
return ;
}
void rotate(int u) {
int y = fa[u], z = fa[y], l = 0, r = 1;
if(z) ch[ch[1][z]==y][z] = u;
if(ch[1][y] == u) swap(l, r);
fa[u] = z; fa[y] = u; fa[ch[r][u]] = y;
ch[l][y] = ch[r][u]; ch[r][u] = y;
maintain(y); maintain(u);
return ;
}
void insert(int& o, int v, char* s) {
if(!o) {
ns[o = ++ToT] = Node(v, rand(), s);
return maintain(o);
}
bool d = ns[o] < Node(v, -1, s);
insert(ch[d][o], v, s); fa[ch[d][o]] = o;
if(ns[ch[d][o]].r > ns[o].r) {
int t = ch[d][o];
rotate(t); o = t;
}
return maintain(o);
}
void del(int& o, int v, char* s) {
if(ns[o] == Node(v, -1, s)) {
if(!ch[0][o] && !ch[1][o]) o = 0;
else if(!ch[0][o]) {
int t = ch[1][o]; fa[t] = fa[o]; o = t;
}
else if(!ch[1][o]) {
int t = ch[0][o]; fa[t] = fa[o]; o = t;
}
else {
bool d = ns[ch[1][o]].r > ns[ch[0][o]].r;
int t = ch[d][o]; rotate(t); o = t;
del(ch[d^1][o], v, s);
}
}
else {
bool d = ns[o] < Node(v, -1, s);
del(ch[d][o], v, s);
}
return maintain(o);
}
Node qkth(int o, int k) {
if(!o) return Node(-1, -1, "233");
int ls = ch[0][o] ? ns[ch[0][o]].siz : 0;
if(k == ls + 1) return ns[o];
if(k > ls + 1) return qkth(ch[1][o], k - ls - 1);
return qkth(ch[0][o], k);
}
int Find(int o, int v, char* s, int k) {
if(!o) return -1;
int ls = (ch[0][o] ? ns[ch[0][o]].siz : 0);
if(ns[o] == Node(v, -1, s)) return k + ls + 1;
bool d = ns[o] < Node(v, -1, s);
return Find(ch[d][o], v, s, k + (ls + 1) * d);
} int main() {
int q = read(), cnts = 0;
while(q--) {
char s[15]; scanf("%s", s);
if(s[0] == '+') {
int tmp = getid(s + 1);
if(tmp) del(rt, sc[tmp], s + 1);
insert(++cnts, s + 1), tmp = cnts;
sc[tmp] = read();
insert(rt, sc[tmp], s + 1);
}
if(s[0] == '?') {
if(isalpha(s[1])) printf("%d\n", Find(rt, sc[getid(s+1)], s + 1, 0));
else {
int l = strlen(s + 1), x = 0;
for(int i = 1; i <= l; i++) x = x * 10 + s[i] - '0';
int mxi = min(x + 9, ns[rt].siz);
for(int i = x; i <= mxi; i++) {
Node t = qkth(rt, i);
printf("%s%c", t.name, i < mxi ? ' ' : '\n');
}
}
}
} return 0;
}