切换到宽版
发帖 回复
返回列表
  • 4339阅读
  • 2回复

SBT我的程序 [复制链接]

 上一主题 下一主题
离线zhuojingwei
OIFans初赛选手
 
只看楼主 倒序阅读 0 发表于: 2008-02-12
复制代码
  1. program lt;
  2. var n,m,num,p,i,k,code,head:longint;
  3.     key,left,right,s:array[1..100000] of longint;
  4.     ss:string;
  7. procedure left_rotate(var x:longint);
  8. var y:longint;
  9. begin
  10.   y:=right[x];
  11.   right[x]:=left[y];
  12.   left[y]:=x;
  13.   s[y]:=s[x];
  14.   s[x]:=s[left[x]]+s[right[x]]+1;
  15.   x:=y;
  16. end;
  18. procedure right_rotate(var x:longint);
  19. var y:longint;
  20. begin
  21.   y:=left[x];
  22.   left[x]:=right[y];
  23.   right[y]:=x;
  24.   s[y]:=s[x];
  25.   s[x]:=s[left[x]]+s[right[x]]+1;
  26.   x:=y;
  27. end;
  29. procedure maintain(var t:longint;flag:boolean);
  30. begin
  31.   if flag then
  32.     if s[right[right[t]]]>s[left[t]] then
  33.           left_rotate(t)
  34.     else
  35.     if s[left[right[t]]]>s[left[t]] then
  36.     begin
  37.       right_rotate(right[t]);
  38.       left_rotate(t);
  39.     end
  40.     else exit
  41.   else
  42.     if s[left[left[t]]]>s[right[t]] then
  43.           right_rotate(t)
  44.     else
  45.     if s[right[left[t]]]>s[right[t]] then
  46.     begin
  47.       left_rotate(left[t]);
  48.       right_rotate(t);
  49.     end
  50.     else exit;
  52.   maintain(left[t],false);
  53.   maintain(right[t],true);
  54.   maintain(t,false);
  55.   maintain(t,true);
  56. end;
  58. procedure insert(k:longint;var t:longint);
  59. begin
  60.   if t=0 then
  61.   begin
  62.     inc(num);
  63.     t:=num;
  64.     s[t]:=1;
  65.     left[t]:=0;right[t]:=0;
  66.     key[t]:=k;
  67.   end
  68.   else
  69.   begin
  70.     inc(s[t]);
  71.     if k<key[t] then insert(k,left[t]) else insert(k,right[t]);
  72.     maintain(t,k>=key[t]);
  73.   end;
  74. end;
  76. function delete(k:longint;var t:longint):longint;
  77. begin
  78.   dec(s[t]);
  79.   if (k=key[t])or(k<key[t])and(left[t]=0)or(k>key[t])and(right[t]=0) then
  80.   begin
  81.     delete:=key[t];
  82.     if (left[t]=0) or (right[t]=0) then t:=left[t]+right[t]
  83.     else key[t]:=delete(k+1,left[t]);
  84.   end
  85.   else
  86.   if k<key[t] then delete:=delete(k,left[t])
  87.   else delete:=delete(k,right[t]);
  88. end;
  90. procedure select(k:longint;var t:longint);
  91. begin
  92.   if k=s[left[t]]+1 then
  93.   begin
  94.     writeln(key[t]);
  95.     p:=delete(key[t],head);
  96.   end
  97.   else if k<=s[left[t]] then select(k,left[t])
  98.   else select(k-1-s[left[t]],right[t]);
  99. end;
  102. begin
  103.   assign(input,'arr.in');
  104.   assign(output,'arr.out');
  105.   reset(input);
  106.   rewrite(output);
  107.   readln(n,m);
  108.   head:=0;
  109.   for i:=1 to m do
  110.   begin
  111.     readln(ss);
  112.     val(copy(ss,3,length(ss)-2),k,code);
  113.     if ss[1]='i' then insert(k,head)
  114.     else select(k,head);
  115.   end;
  116.   close(input);
  117.   close(output);
  118. end.
回复
举报
分享到 淘江湖 新浪 QQ微博 QQ空间 开心 人人 豆瓣 网易微博 百度 鲜果 白社会 飞信
离线zhuojingwei
OIFans初赛选手
只看该作者 1 发表于: 2008-02-13
难道说没人知道SBT吗
回复
举报
离线zhuojingwei
OIFans初赛选手
只看该作者 2 发表于: 2008-03-02
人工再来一下
回复
举报
发帖 回复
返回列表
快速回复
限100 字节
 
上一个 下一个