博客

题目描述：

排名系统通常要应付三种请求：上传一条新的得分记录、查询某个玩家的当前排名以及返回某个区段内的排名记录。当某个玩家上传自己最新的得分记录时，他原有的得分记录会被删除。为了减轻服务器负担，在返回某个区段内的排名记录时，最多返回10条记录。

输入：

略

输出：

略

这题看上去似乎就是一裸数据结构题——其实——也是一道裸数据结构题（众： = = 那你说个蛋啊！

不过这题硬是磨了一天，最后在自己生成的随机数据下发现一个惊天大Bug：

作为Splay的保护节点，把自己的名字”CYB”和某熟人的名字首先添加进了排名列表——分别为最高分和最低分。

于是搞笑的事情发生了——随机数据里面居然也有个叫CYB的！大囧啊！坑人啊！

就因为这个bug一直死循环一直TLE……( ⊙ o ⊙ )啊！ 真是 #^%@%！￥(&^…￥

值得一提的是，splay在某些规则下可能会退化，这个时候随机提根就好了，效果十分不错。

嗯，就是这样……另外Hash如果用Map代替的话会比较舒服。

Code：

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int SD=23333, SN=400010, MD=1000000007, MD1=12333333;
#define L(_) c[_][0]
#define R(_) c[_][1]
 
int n,m,i,j,fen,d,inx,l,r;
int hash[MD1],sz,la;  struct node{int key,nx;} ar[SN];
int c[SN][2],f[SN],size[SN],p[SN],root;
long long hn,hn1;  unsigned rdn=17;
char cmd,str[30],s[SN][30];
 
int getint() {int rn=0;char ch=getchar();while(ch<'0'||ch>'9')ch=getchar();do{rn=rn*10+ch-'0',ch=getchar();}while(ch>='0'&&ch<='9');return rn;}
int getstr(char s[]) {int q=0;char ch=getchar();while(ch==' '||ch=='\n')ch=getchar();while(ch!=' '&&ch!='\n'){s[++q]=ch,ch=getchar();}return q;}
bool hash_find(char s[], int& id)
{
     for(i=1,hn=0; i<=s[0]; i++) 
      hn=(hn*28+s[i]+1-'A')%MD;  
     if(!hash[hn1=hn%MD1]) { hash[hn1]=++sz, ar[sz].key=hn, id=sz; return false; }
     else { for(int j=hash[hn1]; j; la=j,j=ar[j].nx) if(ar[j].key==hn) { id=j; return true; }
            ar[la].nx=++sz, ar[sz].key=hn, id=sz; return false; }
}
void Update(int d) { size[d]=size[L(d)]+size[R(d)]+1; }
void Rotate(int d)
{
     int x=f[d],y=f[x], q=(c[x][0]!=d),p=!q;
     c[x][q]=c[d][p], c[d][p]=x; if(y) c[y][(c[y][0]!=x)]=d;
     f[c[x][q]]=x, f[x]=d, f[d]=y, f[0]=0;
     Update(x); if(x==root) root=d;
}
int Find(int rk)
{
     int sc;
     for(sc=root; size[L(sc)]+1!=rk; )
      if(size[L(sc)]>=rk) sc=L(sc);
      else rk-=size[L(sc)]+1, sc=R(sc);
     return sc;
}
void Splay(int d, int g)
{
     for(; f[d]!=g; Rotate(d)) 
         if(f[f[d]]!=g) if((L(f[f[d]])==f[d])^(L(f[d])==d)) Rotate(d); else Rotate(f[d]);
     Update(d);
}
void Ins(int d)
{
     size[d]=1,L(d)=R(d)=0;  int t;
     for(t=root; c[t][(p[d]<=p[t])]; ) t=c[t][(p[d]<=p[t])];
     c[t][(p[d]<=p[t])]=d, f[d]=t;
     for(int j=d; j; j=f[j]) Update(j);
     rdn=rdn*SD+t;  Splay(rdn%sz+1, 0);
}
void Advc()
{
     str[0]=3, str[1]='Z'+1,str[2]='Z'+1,str[3]='Z'+1, fen=2000000001; root=1;
     if(!hash_find(str, d)) { p[d]=fen; for(j=1,s[d][0]=str[0]; j<=str[0]; j++)s[d][j]=str[j]; }
     str[0]=2, str[1]='Z'+1,str[2]='Z'+1, fen=-1;
     if(!hash_find(str, d)) { p[d]=fen; for(j=1,s[d][0]=str[0]; j<=str[0]; j++)s[d][j]=str[j]; Ins(d); }
}
void Prints(char s[]) { for(int l=1; l<=s[0]; l++) printf("%c", s[l]); }
void DFS(int d, bool cr)
{
     if(L(d)) DFS(L(d), 0);
     Prints(s[d]);
     if(!R(d)&&cr) printf("\n"); else printf(" ");
     if(R(d)) DFS(R(d), cr);
}
int main()
{
     Advc();
     scanf("%d", &n);
     for(int CCC=1; CCC<=n; CCC++)
     {
          do{cmd=getchar();}while(cmd!='+'&&cmd!='?');
          if(cmd=='+')
          { 
               str[0]=getstr(str), fen=getint();
               if(!hash_find(str, d)) { p[d]=fen; for(j=1,s[d][0]=str[0]; j<=str[0]; j++)s[d][j]=str[j]; Ins(d); }
               else
               { 
                    p[d]=fen; Splay(d, 0); Splay(Find(size[L(d)]), root); 
                    R(L(d))=R(d), f[L(d)]=0, f[R(d)]=L(d); 
                    Update(root=L(d)); Ins(d);   
                }
          }
          else
          {
               str[0]=getstr(str);
               if(str[1]<'0'||str[1]>'9') { hash_find(str, d); Splay(d, 0); printf("%d\n", size[L(d)]); }
               else
               { 
                    for(j=1,inx=0; j<=str[0]; j++)inx=inx*10+str[j]-'0'; inx++;
                    l=inx,r=inx+9; if(r>=sz)r=sz-1;  l--,r++;
                    Splay(Find(l), 0);  Splay(Find(r), root);
                    DFS(L(R(root)), 1);
                }
          }
     }
     return 0;
}