注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

z55250825

一只蒟蒻

 
 
 

日志

 
 

【BZOJ1056】【HAOI2008】【排名系统】  

2014-03-17 16:00:16|  分类: 待处理题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
    题目大意:要乃写一个数据结构,维护两个关键字。然后有三个操作:
    1.插入两个关键字,如果之前第一关键字已经有输入则覆盖之前的第一关键字
    2.询问第一关键字,返回第一关键字所对应的第二关键字的rank。
    3.询问按第二关键字排序后从第k位之后最多10个的第一关键字。
    乱搞吗....第一个第二个部分 HASH就可以做了,第二个第三个平衡树即可,查找第K大。用的treap了,话说直接用系统的随机数生成器会不会数据很大的时候很慢...去学习下随机数生成器怎么写去...
     题目有一种特殊情况没有谈到。那就是分数相同应该先输出去谁的.....所以待yy
=============================

program bzoj1056;
const maxn=250000;
      modd=5000001;
type node=record
     son:array[0..1]of longint;
     f,size:longint;
     ran,a:int64;
     b:string;
     end;

var t:array[0..maxn]of node;
    que:array[0..maxn]of longint;
    n,root,tot,l,r,new,now,now2:longint;
    hash:array[0..maxn*20]of int64;
    nam:array[0..maxn*20]of longint;

{function random(p:int64):longint;
var r:int64;
begin
  inc(now);
  if now=21 then now:=0;
  inc(now2);
  if now2=11 then now2:=0;
  r:=(p*ra[now]+rb[now2]*rb[now2])mod modd;
  exit(trunc(r));
end;}

function min(a,b:longint):longint;
begin
  if a<b then exit(a) else exit(b);
end;

function h(s:string):longint;
var len,i:longint;
    hash:int64;
begin
  hash:=0;
  len:=length(s);
  for i:=1 to len do
   hash:=(hash*131+ord(s[i])*ord(s[i]))mod modd;
  exit(trunc(hash));
end;

procedure rotate(p:longint);
var y,w,ww:longint;
begin
  with t[p] do
   begin
     y:=f;
     f:=t[y].f;
     w:=ord(t[y].son[1]=p);
     ww:=ord(t[t[y].f].son[1]=y);
     f:=t[y].f;
     t[t[y].f].son[ww]:=p;
     t[son[w xor 1]].f:=y;
     t[y].son[w]:=son[w xor 1];
     son[w xor 1]:=y;
     t[y].f:=p;
     t[y].size:=t[t[y].son[0]].size+t[t[y].son[1]].size+1;
     size:=t[son[0]].size+t[son[1]].size+1;
   end;
end;

procedure insert(c:int64;b:string);
var p:longint;
begin
  p:=root;
  while t[p].son[ord(c<=t[p].a)]<>0 do
   begin
     inc(t[p].size);
     p:=t[p].son[ord(c<=t[p].a)];
   end;
  if p<>0 then inc(t[p].size);
  new:=que[l];
  l:=(l+1)mod maxn;
  t[new].f:=p;
  t[p].son[ord(c<=t[p].a)]:=new;
  t[new].ran:=random(5000000);
  t[new].a:=c;
  t[new].b:=b;
  t[new].size:=1;
  while (t[new].f<>0)and(t[new].b>t[t[new].f].b)do rotate(new);
  if t[new].f=0 then root:=new;
end;

procedure delete(now:longint;c:int64;b:string);
var p:longint;
begin
  p:=now;
  if tot=1 then
   begin
     que[r]:=p;
     r:=(r+1)mod maxn;
     root:=0;
     t[0].son[0]:=0;
     t[0].son[1]:=0;
     exit;
   end;
  while t[p].f<>0 do
   begin
     dec(t[p].size);
     p:=t[p].f;
   end;
  p:=now;
  while (t[p].son[0]<>0)or(t[p].son[1]<>0)do
   begin
    if (t[t[p].son[0]].ran<t[t[p].son[1]].ran)then rotate(t[p].son[0])
                                              else rotate(t[p].son[1]);
    dec(t[t[p].f].size);
    if root=p then root:=t[p].f;
   end;
  que[r]:=p;
  r:=(r+1)mod maxn;
  t[t[p].f].son[ord(t[t[p].f].son[1]=p)]:=0;
end;

function find(aim:longint):longint;
var p:longint;
begin
  p:=root;
  while true do
   begin
     if t[t[p].son[0]].size+1=aim then exit(p);
     if t[t[p].son[0]].size+1>aim then p:=t[p].son[0]
        else begin
          dec(aim,t[t[p].son[0]].size+1);
          p:=t[p].son[1];
        end;
   end;
end;

function find2(p:longint):longint;
var size:longint;
begin
  size:=t[t[p].son[0]].size+1;
  while t[p].f<>0 do
   begin
     if t[t[p].f].son[1]=p then
       inc(size,t[t[t[p].f].son[0]].size+1);
     p:=t[p].f;
   end;
  exit(size);
end;

procedure init;
var i,len,j:longint;
    ch:char;
    hh,sc:int64;
    s:string;
begin
  readln(n);
  root:=0;now:=-1;now2:=-1;
  fillchar(hash,sizeof(hash),0);
  l:=0;r:=0;tot:=0;
  for i:=0 to maxn-1 do que[i]:=i+1;
  t[0].ran:=maxlongint;
  t[0].size:=0;
  for i:=1 to n do
   begin
     read(ch);
     case ch of
      '+':begin
           read(ch);
           s:='';
           while (ord(ch)>=ord('A'))and(ord(ch)<=ord('Z')) do
            begin
              s:=s+ch;
              read(ch);
            end;
           readln(sc);
           hh:=h(s);
           if hash[hh]=0 then
            begin
              hash[hh]:=sc;
              insert(sc,s);
              inc(tot);
              nam[hh]:=new;
            end
           else
            begin
              delete(nam[hh],hash[hh],s);
              hash[hh]:=sc;
              insert(sc,s);
              nam[hh]:=new;
            end;
          end;
      '?':begin
           read(ch);
           s:='';
           while ((ord(ch)>=ord('A'))and(ord(ch)<=ord('Z'))) or
           ((ord(ch)>=ord('0'))and(ord(ch)<=ord('9'))) do
            begin
              s:=s+ch;
              read(ch);
            end;
           if (ord(s[1])>=ord('A'))and(ord(s[1])<=ord('Z'))then
            begin
              hh:=h(s);
              hh:=nam[hh];
              hh:=find2(hh);
              writeln(hh);
            end
           else
            begin
              len:=length(s);
              hh:=0;
              for j:=len downto 1 do
               hh:=hh*10+ord(s[j])-ord('0');
              for j:=hh to min(hh+9,tot) do
               begin
                 hh:=find(j);
                 write(t[hh].b,' ');
               end;
              writeln;
            end;
            readln;
           end;
     end;
   end;
end;

begin
  //ASSIGN(INPUT,'rank.in');RESET(INPUT);
  assign(output,'rank.out');rewrite(output);
  init;
  //close(input);
  close(output);
end.





  评论这张
 
阅读(65)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017