做一借款撮合网站,文友胜做的网站,批量做网站软件,武进网站建设效果P4291 [HAOI2008] 排名系统
题目大意
有一个排名系统和 n n n次操作#xff0c;操作分为以下三种#xff1a;
Name Score#xff1a;上传一条新的得分记录?Name#xff1a;查询某个玩家的当前排名?Index#xff1a;返回某个区段内的排名记录
当某个玩家上传自己最新…P4291 [HAOI2008] 排名系统
题目大意
有一个排名系统和 n n n次操作操作分为以下三种
Name Score上传一条新的得分记录?Name查询某个玩家的当前排名?Index返回某个区段内的排名记录
当某个玩家上传自己最新的得分记录时他原有的得分记录会被删除。为了减轻服务器负担在返回某个区段内的排名记录时最多返回10条记录。 10 ≤ n ≤ 250000 10\leq n\leq 250000 10≤n≤250000 题解
前置知识Splay平衡树
用平衡树维护分数然后在平衡树上加点、删点、一个数的排名和排名为 k k k的名字。可以用 m a p map map将名字和分数一一对应。
不过我们发现可能会有几个人的分数相同我们考虑如何解决。我们发现人数不会超过 1 0 6 1 10^61 1061那么我们可以将每个人的分数 w w w变为 w ∗ ( 1 0 6 1 ) k w*(10^61)k w∗(1061)k其中 k k k是一个随着操作次数的增加二减少的数这就解决了分数相同的问题。
code
#includebits/stdc.h
using namespace std;
const int N500000;
int T,s1,nt;
int rt,tot,cnt[N5],siz[N5],fa[N5],ch[N5][2];
long long mt[N5];
char s[105];
string nm[N5];
mapstring,intmp;
struct node{long long v;int wt;bool operator(const node ax)const{return vax.v;}bool operator(const node ax)const{return vax.v;}bool operator!(const node ax)const{return v!ax.v;}
}v[N5];
int gt(int x){return ch[fa[x]][1]x;
}
void pt(int x){siz[x]1siz[ch[x][0]]siz[ch[x][1]];
}
void rot(int x){int yfa[x],zfa[y],kgt(x);ch[z][gt(y)]x;fa[x]z;ch[y][k]ch[x][!k];fa[ch[y][k]]y;ch[x][!k]y;fa[y]x;pt(y);pt(x);
}
void splay(int x,int g0){for(int y;fa[x]!g;rot(x)){yfa[x];if(fa[y]!g) rot((gt(y)gt(x))?y:x);}if(!g) rtx;
}
void find(long long x){if(!rt) return;int urt;while(ch[u][(node){x,0}v[u]](node){x,0}!v[u]) uch[u][(node){x,0}v[u]];splay(u);
}
void insert(long long x,int wt){int urt,fu0;while(uv[u]!(node){x,0}){fuu;uch[u][(node){x,0}v[u]];}utot;if(fu) ch[fu][(node){x,0}v[fu]]u;fa[u]fu;v[u](node){x,wt};siz[u]1;splay(u);
}
int nxt(long long x,int f){find(x);int urt;if(v[u](node){x,0}f) return u;if(v[u](node){x,0}!f) return u;uch[u][f];while(ch[u][!f]) uch[u][!f];return u;
}
void dele(long long x){int ltnxt(x,0),rtnxt(x,1);splay(lt);splay(rt,lt);ch[rt][0]0;
}
int kth(int k){int urt,sn0;for(;;){snch[u][0];if(ksiz[sn]1) k-siz[sn]1,uch[u][1];else if(siz[sn]k) usn;else{splay(u);return v[u].wt;}}
}
int main()
{insert(1e18,0);insert(-1e18,0);scanf(%d,T);while(T--){scanf(%s,s);s1strlen(s);int tp0;string t;long long w;if(s[0]){for(int i1;is1;i) tts[i];scanf(%lld,w);ww*(N1)T;if(mp.count(t)){dele(mt[mp[t]]);}else{nm[nt]t;mp[t]nt;}mt[mp[t]]w;insert(w,mp[t]);}else if(s[1]0||s[1]9){for(int i1;is1;i) tts[i];find(mt[mp[t]]);int tmpsiz[ch[rt][0]](v[rt](node){mt[mp[t]],0});printf(%d\n,nt-tmp1);}else{for(int i1;is1;i) tptp*10s[i]-0;tpnt-tp1;for(int itp;imax(tp-101,1);i--){coutnm[kth(i1)] ;}printf(\n);}}return 0;
}
