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

• PASCAL和C的效率差这么多？ (0) js05 2005-05-13 15:24:06