> 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的复杂度？

• 我还是换线段树吧，请各位赐教为什么这方法这么慢。。。 (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