type point=record
             x,y:longint;
           end;

var ps:array [1..15000] of point;
    num:array [0..14999] of longint;
    c:array [1..32001] of longint;
    n,limit:longint;

procedure init;
var i:longint;
begin
  readln(n);
  limit:=0;
  for i:=1 to n do
  begin
    readln(ps[i].x,ps[i].y);
    inc(ps[i].x);
    inc(ps[i].y);
    if ps[i].y>limit then
      limit:=ps[i].y;
  end;
end;

procedure swap(var a,b:point);
var c:point;
begin
  c:=a;
  a:=b;
  b:=c;
end;

procedure qsort(s,t:longint);
var i,j:longint;
    x:point;
begin
  swap(ps[s],ps[s+random(t-s)+1]);
  i:=s;
  j:=t;
  x:=ps[s];
  while i<j do
  begin
    while ((ps[j].x>x.x) or ((ps[j].x=x.x) and (ps[j].y>x.y))) and (j>i) do
      dec(j);
    if i<j then
    begin
      ps[i]:=ps[j];
      inc(i);
    end;
    while ((ps[i].x<x.x) or ((ps[i].x=x.x) and (ps[i].y<x.y))) and (i<j) do
      inc(i);
    if j>i then
    begin
      ps[j]:=ps[i];
      dec(j);
    end;
    ps[i]:=x;
  end;
  if s<pred(i) then
    qsort(s,pred(i));
  if succ(i)<t then
    qsort(succ(i),t);
end;

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

procedure insert(x:longint);
begin
  while x<=limit do
  begin
    inc(c[x]);
    inc(x,lowbit(x));
  end;
end;

function sum(x:longint):longint;
begin
  sum:=0;
  while x>0 do
  begin
    inc(sum,c[x]);
    dec(x,lowbit(x));
  end;
end;

procedure main;
var i:longint;
begin
  filldword(num,sizeof(num) div 4,0);
  filldword(c,sizeof(c) div 4,0);
  for i:=1 to n do
  begin
    inc(num[sum(ps[i].y)]);
    insert(ps[i].y);
  end;
end;

procedure print;
var i:longint;
begin
  for i:=0 to n-1 do
    writeln(num[i]);
end;

begin
  init;
  qsort(1,n);
  main;
  print;
end.

莫非此代码不是nlogn的复杂度？

• TLE是事实，但我想搞清楚，为什么会这么慢。。。 (2081) js05 2005-05-13 15:12:40
  • 我还是换线段树吧，请各位赐教为什么这方法这么慢。。。 (0) js05 2005-05-13 15:19:50
  • 怎么要排序？用不着吧？连纵坐标都可以不用的，只要一个x就够了 (0) frkstyc 2005-05-13 15:23:52
    • 怎么搞，我不明白。。。 (0) js05 2005-05-13 15:25:26
      • p1<p2，不是要p1.x<=p2.x and p1.y<=p2.y 吗？ (0) js05 2005-05-13 15:26:25
        • 数据保证先对y有序然后对x有序 (0) frkstyc 2005-05-13 15:27:46
          • 原来是这样。。。没好好读题，傻了。。。 (0) js05 2005-05-13 15:29:06
            • 拿qsort去排顺序的数据肯定超时了 (0) frkstyc 2005-05-13 15:29:45
              • 不过我qsort的时候随机了呀，效率也不应该差这么多。。。 (0) js05 2005-05-13 15:40:04
                • 那你不如用冒泡去排，跑一趟就可以停下来了 (0) frkstyc 2005-05-13 15:44:45
                  • 哈哈，确实！总之，我干了一件SB的事情。。。 (0) js05 2005-05-13 15:51:34
      • 把排序整段拿掉就基本上可以了，可能在边界处要调整一下 (0) frkstyc 2005-05-13 15:27:07
• 我也是这样做的，C写的105ms，汇编好像也好不了多少，90ms (2081) frkstyc 2005-05-13 15:22:35
  • PASCAL和C的效率差这么多？ (0) js05 2005-05-13 15:24:06