Archive for 六月 24th, 2008

SGU 180 — Inversions

Posted on 六月 24th, 2008.

求逆序对个数,很经典了.可以归并排序求,可我不喜欢归并,所以我的做法是离散化之后用树状数组维护一下.复杂度一样,离散化也不是很难写,树状数组也巨简单.强烈推荐.
这题极其bt的是,答案是int64的…用longint存答案就WA on 14(还是12?)…
{ SGU 180; Inversions - sqybi’s code - 逆序对}//for my winstyprogram 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;    […]