纪念树状数组初步（……）；

这题已经给了y升序，y相同时x升序，（yeah）

所以容易想到O(n^2)的模拟算法；

其实分析一下就是对于当前xi,统计之前有多少个小于等于xi(因为已经保证了没有相同坐标的点）

初学者（比如我），一开始感觉和树状数组没毛关系，但是……

仔细想想发现，树状数组是修改和区间求值的，我们能不能将问题转化呢？

可以！这里用到类似计数排序的思想，a数组表示对x可能出现的范围内中每个数表示的次数；

则：对于当前xi,之前小于等于xi的个数就等于sigma(a[0]~a[x[i]]) 

这下子就变成树状数组拿手的区间求和了！

但注意细节，因为存在x=0,但构建树状数组下标是从1开始的

所以我们把所有x加1即可，不影响位置之间的关系。

1 var x,y,ans,b:array[0..20000] of longint; 2     c:array[0..40000] of longint; 3     maxx,i,n:longint; 4 function lowbit(x:longint):longint;   //树状数组的核心 5   begin 6     lowbit:=x and -x; 7   end; 8 function ask(x:longint):longint;     //区间求和 9   begin10     ask:=0;11     while x<>0 do12     begin13       ask:=ask+c[x];14       x:=x-lowbit(x);15     end;16   end;17 procedure work(x:longint);          //更改单点时，注意把父亲节点也要更新18   begin19     while x<=maxx do20     begin21       inc(c[x]);22       x:=x+lowbit(x);23     end;24   end;25 26 begin27   readln(n);28   for i:=1 to n do29   begin30     readln(x[i],y[i]);31     inc(x[i]);32     if x[i]>maxx then maxx:=x[i];             //限定范围33   end;34   for i:=1 to n do35   begin36     b[i]:=ask(x[i]);37     work(x[i]);38   end;39   for i:=1 to n do40     inc(ans[b[i]]);41   for i:=0 to n-1 do42     writeln(ans[i]);43 end.

相对于线段树，树状数组实现还是很简单的，时空复杂度也不错！