首页 > 代码库 > Bzoj1056--Haoi2008排名系统
Bzoj1056--Haoi2008排名系统
平衡树练习
还是很水的一道题（雾
反正字符串哈希一下会方便很多，其它都是常规操作也没什么好说的
平衡树写得挺繁杂的，以后可能去想想精简一点的版本，写是难写，但这种题一般写出来了就不会错（说完就PE了。。
代码：
#include<bits/stdc++.h>#define MAXN 250005#define MAXM 3005#define INF 10000000000000LL#define MOD 1000003#define LL long longusing namespace std;inline int Hash(char *s) { int ret=0; for(int i=strlen(s)-1;i>0;i--) ret=ret*27+s[i]-‘A‘+1,ret%=MOD; return ret;}struct elem{ char s[15];int v;};vector<elem> table[MOD];inline int _find(char *s) { int k=Hash(s);int lim=table[k].size(),ret=0; for(int i=0;i<lim;i++) { if(!strcmp(table[k][i].s+1,s+1)) ret=table[k][i].v; } return ret;}int n,bk[MAXN];char s[15];struct Node { int son[2],par,sz;LL v,r;}x[MAXN];struct Treap{ int root,L,R,cnt; void init() { root=MAXN-2;L=0;R=1;cnt=0; x[root].v=INF;x[root].r=INF; } int pa,t; inline void rotate(int num,int p) { pa=x[num].par;t=x[num].sz; x[num].sz=x[pa].sz;x[pa].sz-=t-x[x[num].son[p]].sz; x[x[pa].par].son[x[x[pa].par].son[L]==pa?L:R]=num;x[num].par=x[pa].par; x[pa].son[p^1]=x[num].son[p];if(x[num].son[p]) x[x[num].son[p]].par=pa; x[pa].par=num;x[num].son[p]=pa; } void Del(int num) { while(x[num].son[R]|x[num].son[L]) if(x[x[num].son[R]].r>x[x[num].son[L]].r) rotate(x[num].son[R],L); else rotate(x[num].son[L],R); int now=x[num].par; while(now) {x[now].sz--;now=x[now].par;} x[x[num].par].son[x[x[num].par].son[L]==num?L:R]=0; } void Insert(int num,int v) { int now=root,pre; x[num].sz=1;x[num].r=rand()%MOD;x[num].v=v; while(true) { pre=v>x[now].v?L:R;x[now].sz++; if(!x[now].son[pre]) {x[num].par=now;x[now].son[pre]=num;break;} now=x[now].son[pre]; } while(x[num].r>x[x[num].par].r) rotate(num,x[x[num].par].son[L]==num?R:L); } void Updata(int num,int v,char *s) { if(!num) { int k=Hash(s);elem t;strcpy(t.s,s);t.v=++cnt; table[k].push_back(t),num=cnt;bk[cnt]=k; } Del(num);Insert(num,v); } bool Qurey_Treap(int v,int p) { if(x[root].sz<v) return 0; int now=x[root].son[R],lim; while(true) { if(x[x[now].son[L]].sz==v-1) break; if(x[x[now].son[L]].sz<v) v-=x[x[now].son[L]].sz+1,now=x[now].son[R]; else now=x[now].son[L]; } lim=table[bk[now]].size(); for(int i=0;i<lim;i++) if(table[bk[now]][i].v==now) { if(p) printf(" %s",table[bk[now]][i].s+1); else printf("%s",table[bk[now]][i].s+1); return 1; } } inline void Qurey_P(int num) { int ret=x[x[num].son[L]].sz,now=num; while(now) { if(x[x[now].par].son[R]==now) ret+=x[x[x[now].par].son[L]].sz+1; now=x[now].par; } printf("%d\n",ret); } inline void Qurey_R(int k) { for(int i=0;i<10;i++) if(!Qurey_Treap(k+i,i)) break;printf("\n"); }};int main() { srand(2333333); scanf("%d",&n); Treap p;p.init(); LL a; for(int i=1;i<=n;i++) { scanf("%s",s); if(s[0]==‘+‘) {scanf("%lld",&a);p.Updata(_find(s),a,s);} if(s[0]==‘?‘) { if(s[1]>‘9‘) p.Qurey_P(_find(s)); else { int len=strlen(s);a=0; for(int i=1;i<len;i++) a=a*10+s[i]-‘0‘; p.Qurey_R(a); } } } return 0;}
Bzoj1056--Haoi2008排名系统
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。