ac1176.pas

某牛人写的acm.tongji.edu.cn上大部分ac的代码,仅供学习研究,请不要用来作弊

program tju1176;
const
  maxn=10000;
type
  list=array[1..maxn]of longint;
var
  a,b:list;
  t,u,n,i,ans:longint;
procedure merge_sort(var a,b:list;s,t:word);
  var
    m,p,q,i:word;
  begin
    if s=t then exit;
    m:=(s+t) shr 1;p:=s;q:=m+1;
    merge_sort(b,a,s,m);merge_sort(b,a,q,t);
    for i:=s to t do
      if (p>m) or (q<=t) and (b[q]<b[p]) then begin
        a[i]:=b[q];inc(q);inc(ans,m-p+1);
      end
      else begin
        a[i]:=b[p];inc(p);
      end;
  end;
begin
  read(t);
  for u:=1 to t do begin
    read(n);
    for i:=1 to n do begin
      read(a[i]);b[i]:=a[i];
    end;
    ans:=0;
    merge_sort(a,b,1,n);
    writeln(ans);
  end;
end.