| 记录编号 |
244260 |
评测结果 |
AAAAAAAAAAA |
| 题目名称 |
[HAOI 2008]排名系统 |
最终得分 |
100 |
| 用户昵称 |
 Fmuckss |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
1.523 s |
| 提交时间 |
2016-03-31 17:57:03 |
内存使用 |
7.94 MiB |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<string>
#include<string.h>
#include<map>
#include<vector>
using namespace std;
typedef unsigned int UI;
const int maxn = 2.5e5;
string stor[maxn];
inline UI hash(int &num) {
UI b = 378551;
UI a = 63689;
UI hash = 0;
for(int i = 0; i < stor[num].length(); i++) {
hash = hash*a + stor[num][i];
a *= b;
}
return hash;
}
inline UI hash_s(string s) {
UI b = 378551;
UI a = 63689;
UI hash = 0;
for(string::iterator it = s.begin(); it != s.end(); ++it) {
hash = hash*a + *it;
a *= b;
}
return hash;
}
int t;
int n;
map<UI, int> m;
int r[maxn];
inline void outs(int &tar) {
for(int i = 0; i < stor[tar].length(); i++) {
putchar(stor[tar][i]);
}
}
struct infor {
int num, rate;
inline infor() {num = 0; rate = 0;}
inline infor(int num_, int rate_) {num = num_, rate = rate_;}
inline bool operator < (const infor &b) const {
return rate == b.rate ? num < b.num : rate > b.rate;//num小的优先级高，rate大的优先级高
}
inline bool operator == (const infor &b) const {
return rate == b.rate & num == b.num;
}
};
template <class T> class splay_tree {
private:
struct node {
int ls, rs, fa, sz;
T v;
inline node() {}
inline node(int ls_, int rs_, int fa_, int sz_, T v_) { ls = ls_, rs = rs_, fa = fa_, sz = sz_, v = v_; }
}ns[maxn];
int tot;
int cnt;
public:
inline splay_tree () { tot = 0; }
inline int size() { return ns[ns[0].ls].sz; }
inline int new_node() { return ++tot; }
inline void insert_root(T tar) {
ns[0].ls = new_node();
ns[ns[0].ls] = node(0, 0, 0, 1, tar);
}
inline void zig(const int &tar) {
int tmp = ns[tar].fa;
if(tmp == ns[ns[tmp].fa].ls) ns[ns[tmp].fa].ls = tar;
else ns[ns[tmp].fa].rs = tar;
ns[tar].fa = ns[tmp].fa;
ns[tmp].ls = ns[tar].rs;
if(ns[tar].rs) ns[ns[tar].rs].fa = tmp;
ns[tar].rs = tmp, ns[tmp].fa = tar;
ns[tmp].sz = ns[ns[tmp].ls].sz + ns[ns[tmp].rs].sz+1;
}
inline void zag(const int &tar) {
int tmp = ns[tar].fa;
if(tmp == ns[ns[tmp].fa].ls) ns[ns[tmp].fa].ls = tar;
else ns[ns[tmp].fa].rs = tar;
ns[tar].fa = ns[tmp].fa;
ns[tmp].rs = ns[tar].ls;
if(ns[tar].ls) ns[ns[tar].ls].fa = tmp;
ns[tar].ls = tmp, ns[tmp].fa = tar;
ns[tmp].sz = ns[ns[tmp].ls].sz + ns[ns[tmp].rs].sz+1;
}
inline void splay(const int &now, const int &to) {
if(now == to) return;
bool done = false;
int fa;
while(!done) {
fa = ns[now].fa;
if(fa == to) {
done = true;
ns[fa].ls == now ? zig(now) : zag(now);
} else {
if(ns[fa].fa == to) done = true;
if(ns[ns[fa].fa].ls == fa) (ns[fa].ls == now ? zig(fa) : zag(now)), zig(now);
else (ns[fa].ls == now ? zig(now) : zag(fa)), zag(now);
}
}
ns[now].sz = ns[ns[now].ls].sz + ns[ns[now].rs].sz + 1;
}
inline void insert(T tar) {
int now = ns[0].ls;
if(!now) { insert_root(tar); return; }
while(true) {
if(tar < ns[now].v) {
if(!ns[now].ls) {
int tmp = new_node();
ns[now].ls = tmp;
ns[tmp] = node(0, 0, now, 1, tar);
splay(tmp, ns[0].ls);
return;
}
else now = ns[now].ls;
} else {
if(!ns[now].rs) {
int tmp = new_node();
ns[now].rs = tmp;
ns[tmp] = node(0, 0, now, 1, tar);
splay(tmp, ns[0].ls);
return;
}
else now = ns[now].rs;
}
}
}
inline int find(T &tar) {
int now = ns[0].ls;
while(true) {
if(ns[now].v == tar)
break;
else if(tar < ns[now].v)
now = ns[now].ls;
else
now = ns[now].rs;
}
splay(now, ns[0].ls);
return now;
}
inline int get_max(int &ac) {
int now = ac;
while(true) {
if(ns[now].rs) now = ns[now].rs;
else break;
}
splay(now, ac);
return now;
}
inline void del(T tar) {
int now = find(tar);
int ls, rs;
ls = ns[now].ls;
rs = ns[now].rs;
if(!ls) {
ns[ns[now].fa].ls == now ? ns[ns[now].fa].ls = rs : ns[ns[now].fa].rs = rs;
if(rs) ns[rs].fa = ns[now].fa;
return;
}
ls = get_max(ls);
ns[ns[now].fa].ls == now ? ns[ns[now].fa].ls = ls : ns[ns[now].fa].rs = ls;
ns[ls].fa = ns[now].fa;
if(rs) ns[rs].fa = ls;
ns[ls].rs = rs;
ns[ls].sz = ns[ns[ls].ls].sz + ns[ns[rs].rs].sz + 1;
}
inline int get_rank(T tar) {
int now = find(tar);
return ns[ns[now].ls].sz+1;
}
inline void out(int tar) {
int now = ns[0].ls;
while(true) {
if(ns[ns[now].ls].sz+1 == tar) break;
if(tar > ns[ns[now].ls].sz+1) {
tar -= ns[ns[now].ls].sz+1;
now = ns[now].rs;
}
else now = ns[now].ls;
}
splay(now, ns[0].ls);
outs(ns[now].v.num);
putchar(' ');
}
};
inline int get_num() {
int ans = 0;
char tmp = getchar();
while(tmp < '0' || tmp > '9') tmp = getchar();
while(tmp <= '9' && tmp >= '0') {
ans = 10*ans + tmp - '0';
tmp = getchar();
}
return ans;
}
inline string get_string() {
string ans;
ans.clear();
char tmp = getchar();
while(tmp < 'A' || tmp > 'Z') tmp = getchar();
while(tmp <= 'Z' && tmp >= 'A') {
ans = ans + tmp;
tmp = getchar();
}
return ans;
}
inline char get_han() {
char tmp = getchar();
while(tmp != '+' && tmp != '?')
tmp = getchar();
return tmp;
}
splay_tree <infor> spt;
inline void solve() {
n = get_num();
char han;
string name;
int rate;
int tar;
for(int i = 1; i <= n; i++) {
han = get_han();
if(han == '+') {
name = get_string();
rate = get_num();
stor[i] = name;
r[i] = rate;
UI h = hash(i);
tar = m[h];
if(tar) {//如果已经存在
spt.del(infor(tar, r[tar]));//删除原有节点 ,假装不存在
}
m[h] = i;
spt.insert(infor(i, rate));
} else {
char tmp = getchar();
while((tmp < '0' || tmp > '9') && (tmp > 'Z' || tmp < 'A')) tmp = getchar();
if(tmp <= '9' && tmp >= '0') {
tar = 0;
while(tmp <= '9' && tmp >= '0') {
tar = 10*tar + tmp - '0';
tmp = getchar();
}
int size = min(tar+9, spt.size());
for(int i = tar; i <= size; i++) {
spt.out(i);
}
putchar('\n');
} else {
name.clear();
while(tmp <= 'Z' && tmp >= 'A') {
name = name + tmp;
tmp = getchar();
}
tar = m[hash_s(name)];
printf("%d\n",spt.get_rank(infor(tar, r[tar])));
}
}
}
}
int main() {
freopen("rank.in", "r", stdin);
freopen("rank.out", "w", stdout);
solve();
return 0;
}