NOT A BLOG | sqybi

SGU 180 — Inversions

Posted on 六月 24th, 2008.

求逆序对个数,很经典了.可以归并排序求,可我不喜欢归并,所以我的做法是离散化之后用树状数组维护一下.复杂度一样,离散化也不是很难写,树状数组也巨简单.强烈推荐.

这题极其bt的是,答案是int64的…用longint存答案就WA on 14(还是12?)…

{
SGU 180; Inversions
- sqybi’s code
- 逆序对
}
//for my winsty
program sgu180_sqybi;
  const
    nn = 65537;

  type
    rec = record
      v, p: longint;
    end;

  var
    n, i, t, r: longint;
    s: int64;
    a: array[1..nn]of rec;
    b, c: array[1..nn]of longint;

  procedure qsort(l, r: longint);
    var
      i, j, d: longint;
      t: rec;
    begin
      if l >= r then exit;
      i := l;
      j := r;
      d := a[(l+r) div 2].v;
      repeat
        while a[i].v < d do inc(i);
        while a[j].v > d do dec(j);
        if i <= j then begin
          t := a[i];
          a[i] := a[j];
          a[j] := t;
          inc(i);
          dec(j);
        end;
      until i > j;
      qsort(l, j);
      qsort(i, r);
    end;

  function lowbit(x: longint): longint;
    begin
      lowbit := x and -x;
    end;

  procedure add(x: longint);
    begin
      while x <= n do begin
        inc(c[x]);
        x := x + lowbit(x);
      end;
    end;

  function sum(x: longint): int64;
    var
      s: longint;
    begin
      s := 0;
      while x > 0 do begin
        s := s + c[x];
        x := x - lowbit(x);
      end;
      sum := s;
    end;

  begin
    readln(n);
    for i:=1 to n do begin
      read(a[i].v);
      a[i].p := i;
    end;
    qsort(1, n);
    t := n;
    r := a[1].v;
    a[1].v := t;
    for i:=2 to n do begin
      if a[i].v <> r then dec(t);
      r := a[i].v;
      a[i].v := t;
    end;

    for i:=1 to n do
      b[a[i].p] := a[i].v;

    s := 0;
    fillchar(c, sizeof(c), 0);
    for i:=1 to n do begin
      s := s + sum(b[i]-1);
      add(b[i]);
    end;
    writeln(s);
  end.

阅读(90 次)

Make a Comment

Make A Comment: ( 2 so far )

2 Responses to “SGU 180 — Inversions”

Comments RSS Feed

Where's The Comment Form?