【BZOJ1056/1862】【排名系统】【hash+treap】

N<=250000

题解：对于treap的每个节点维护一个权值和时间.

            寻找名字可以用hash+链表.

            剩下的都是些基本操作了.

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#define N 500010
#define P 23333
using namespace std;
int n,point[N],next[N],cnt,sz,root;
long long x;
char ch[12];
struct treap{int l,r,s,rd,time;long long v; 	char ch[12];
}tr[N];
struct hash{int time;long long v;char ch[12];}p[N];
void update(int k){tr[k].s=tr[tr[k].l].s+tr[tr[k].r].s+1;}
bool judge(char a[],char b[]){int len=max(strlen(a),strlen(b));for (int i=1;i<len;i++) if (a[i]!=b[i]) return 0;return 1;
}
int cal(char ch[]){int ans(0),len=strlen(ch);//cout<<ans<<' '<<ch<<endl;for (int i=1;i<len;i++)ans=(ans*29+ch[i]-'A')%P;return ans;
}
//-----------------------------------------------------//
void lturn(int &k){int t=tr[k].r;tr[k].r=tr[t].l;tr[t].l=k;tr[t].s=tr[k].s;update(k);k=t;  	
}
void rturn(int &k){int t=tr[k].l;tr[k].l=tr[t].r;tr[t].r=k;tr[t].s=tr[k].s;update(k);k=t;
}
void insert(int &k,char ch[],long long v,int time){if (k==0){tr[k=++sz].v=v;tr[k].time=time;memcpy(tr[k].ch,ch,strlen(ch));tr[k].rd=rand();tr[k].s=1;return;}	tr[k].s++;if (v<=tr[k].v){                            insert(tr[k].l,ch,v,time);                                  if (tr[tr[k].l].rd<tr[k].rd) rturn(k);                             }else{insert(tr[k].r,ch,v,time);if (tr[tr[k].r].rd<tr[k].rd) lturn(k);}
}
void del(int &k,char ch[],long long v,int time){if (tr[k].v==v){if (tr[k].time==time){if (tr[k].l*tr[k].r==0) k=tr[k].l+tr[k].r;else if (tr[tr[k].l].rd<tr[k].rd){rturn(k);del(k,ch,v,time);}else{lturn(k);del(k,ch,v,time);}}else if (tr[k].time<time){tr[k].s--;del(tr[k].l,ch,v,time);}else {tr[k].s--;del(tr[k].r,ch,v,time);}}else if (v<=tr[k].v){tr[k].s--;del(tr[k].l,ch,v,time);}else {tr[k].s--;del(tr[k].r,ch,v,time);} 
}
int getrank(int k,long long v,int time){if (k==0) return 0; if (tr[k].v==v){if (tr[k].time>time) return getrank(tr[k].r,v,time);else if (tr[k].time<time) return getrank(tr[k].l,v,time)+tr[tr[k].r].s+1;else return tr[tr[k].r].s+1;}else if (v<tr[k].v) return getrank(tr[k].l,v,time)+tr[tr[k].r].s+1;else return getrank(tr[k].r,v,time);	
}
int find(int k,int rk){if (tr[tr[k].r].s+1==rk) return k;else if (rk<=tr[tr[k].r].s) return find(tr[k].r,rk);else return find(tr[k].l,rk-tr[tr[k].r].s-1);
}
//-----------------------------------------------------------------//
void ins(char ch[],int time,long long v){int t=cal(ch);for (int i=point[t];i;i=next[i])if (judge(ch,p[i].ch)){del(root,p[i].ch,p[i].v,p[i].time);p[i].v=x;p[i].time=time;insert(root,ch,v,time);return;} next[++cnt]=point[t];point[t]=cnt;p[cnt].v=v;p[cnt].time=time;memcpy(p[cnt].ch,ch,strlen(ch));insert(root,ch,v,time);
}
int getp(char ch[]){int t=cal(ch);for (int i=point[t];i;i=next[i])if (judge(ch,p[i].ch))return i;
}
void query1(char ch[]){int t=getp(ch);printf("%d\n",getrank(root,p[t].v,p[t].time));
}
void query2(char ch[]){int t(0),len=strlen(ch);for (int i=1;i<len;i++) t=t*10+ch[i]-'0';for (int i=t;i<=t+9&&i<=cnt;i++){printf("%s",tr[find(root,i)].ch+1);if (i!=cnt&&i!=t+9) printf(" ");}puts("");	
}
int main(){scanf("%d",&n);for (int i=1;i<=n;i++){scanf("%s",ch);if (ch[0]=='+') scanf("%lld",&x),ins(ch,i,x);else if (ch[1]>='A'&&ch[1]<='Z') query1(ch);else query2(ch); }
}