ac1134.pas

同济大学 Online在线题库 AC源代码合集 程序设计竞赛必看资料

program tju1134;
const
  maxn=20000;
  treesize=32767;
var
  a,h:array[1..maxn]of longint;
  tree:array[1..treesize]of word;
  n,i,root:word;
procedure qsort(s,t:word);
  var
    p,i,j,th:longint;
  begin
    if s>=t then exit;
    p:=s+random(t-s+1);
    th:=h[p];h[p]:=h[s];
    i:=s;j:=t;
    repeat
      while (i<j) and (h[j]>th) do dec(j);
      if i=j then break;h[i]:=h[j];inc(i);
      while (i<j) and (h[i]<th) do inc(i);
      if i=j then break;h[j]:=h[i];dec(j);
    until i=j;
    h[i]:=th;
    qsort(s,i-1);
    qsort(i+1,t);
  end;
function search(x:longint):word;
  var
    l,r,m:word;
  begin
    l:=1;r:=n;
    repeat
      m:=(l+r) shr 1;
      if x=h[m] then break else if x<h[m] then r:=m-1 else l:=m+1;
    until false;
    search:=m;
  end;
procedure ins(x:longint);
  var
    p,d,c:word;
  begin
    p:=root;d:=root shr 1;c:=0;
    while (p>n) or (h[p]<>x) do begin
      if (p>n) or (h[p]>x) then begin
        inc(tree[p]);
        dec(p,d);
      end
      else begin
        inc(c,tree[p]-tree[p+d]);
        inc(tree[p]);
        inc(p,d);
      end;
      d:=d shr 1;
    end;
    inc(tree[p]);
    if d>0 then inc(c,tree[p-d]);
    writeln(c);
  end;
begin
  repeat
    fillchar(tree,sizeof(tree),0);
    read(n);
    root:=1;while root*2<=n do root:=root*2;
    for i:=1 to n do begin read(a[i]);h[i]:=a[i];end;
    qsort(1,n);
    for i:=1 to n do
      ins(a[i]);
  until seekeof;
end.