pku2352 Stars

平面中n个点，求每个点左下点的数量，直接上树状数组，题目数据以y为第一关键字，x为第二关键字升序排列了，所以只需从1到n依次插入横坐标，统计之前的小于当前点的横坐标的点数即可，注意树状数组上限是坐标最大值，不是n，同时坐标还有0的可能，所以都加1才行。

View Code

 1 program pku2352(input,output);
 2 var
 3    c          : array[0..40000] of longint;
 4    x,y,answer : array[0..40000] of longint;
 5    n,maxx     : longint;
 6 procedure init;
 7 var
 8    i : longint;
 9 begin
10    maxx:=0;
11    readln(n);
12    for i:=1 to n do
13    begin
14       readln(x[i],y[i]);
15       inc(x[i]);
16       if x[i]>maxx then
17      maxx:=x[i];
18    end;
19 end; { init }
20 function lowbit(x :longint ):longint;
21 begin
22    exit(x and(-x));
23 end; { lowbit }
24 procedure insect(pos,w: longint );
25 begin
26    while pos<=maxx do
27    begin
28       inc(c[pos],w);
29       pos:=pos+lowbit(pos);
30    end;
31 end; { insect }
32 function find(pos :longint ):longint;
33 begin
34    find:=0;
35    while pos>0 do
36    begin
37       inc(find,c[pos]);
38       pos:=pos-lowbit(pos);
39    end;
40 end; { find }
41 procedure main;
42 var
43    i : longint;
44 begin
45    for i:=1 to n do
46    begin
47       inc(answer[find(x[i])]);
48       insect(x[i],1);
49    end;
50 end; { main }
51 procedure print;
52 var
53    i : longint;
54 begin
55    for i:=0 to n-1 do
56       writeln(answer[i]);
57 end; { print }
58 begin
59    init;
60    main;
61    print;
62 end.