题意：给出一堆坐标点，求小于每一个坐标的坐标个数。

分析：这个题显然也不能遍历，数据太大，会超时。

从poj2299，知道树状数组可以用来求一个排列中array[i]前面小于等于array[i]的个数。

例如array[i]= 9 1 0 5 4

通过树状数组可以知道：

array[1]=9--->1   即坐标小于等于1中比9小的个数为1.

array[4]=5--->3   即坐标小于等于4中比5小的个数为3.

具体怎么求呢？2299中也说过，构建树状数组时要将array[]进行排列，然后对对应的number号进行处理，即：

1.要求原来顺序 9 1 0 5 4，前面小于等于array[i]的个数，先离散化：

 array[] 9 1 0 5 4

 numer 1 2 3 4 5

2.有小到大排序

array[]   0 1 4 5 9

number  3 2 5 4 1

3.遍历number进行处理即可。

这个题要求所有的小于某个坐标的数量，因此需要对坐标进行从小到大排序,例如：

(1,1) (5,1) (7,1) (3,3) (5,5)

y 1 1 1 3 5

x 1 5 7 3 5

题目一开始就按坐标排好序，这样找比自己小的坐标就完全转化成一维的(x轴)

x     1 5 7 3 5

ans  1 2 3 2 3

这样将x轴排序，运用上述的方法就可。

得出的getsum(3)=3表示array前三项中小于等于array[3]的个数

同理先以x轴排好序，将二维转化成y轴的一维也可以。

注意：

1.因为坐标不包括它本身，因此需要减一.

2.排序时的问题：

x       1 5 7 3 5

num   1 2 3 4 5

排序后：

x      1 3 5 5 7

num 1 4 2 5 3

这里有重复数字5，排序后必须保证稳定的。因此需要写cmp函数进行规定。

网上还有一种没有离散的做法，这是因为0<=X,Y<=32000，范围比较小，如果上限开到9999999999则必须离散化。

代码：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 using namespace std; 6 //188ms 7 const int maxnum=15001; 8 struct node 9 {10     int digit;11     int number;12 }array[maxnum];13 int tree[maxnum];14 int res[maxnum];15 int n;16 17 void update(int index,int add)18 {19     while(index<=n)20     {21         tree[index]+=add;22         index+=(-index)&index;23     }24 }25 26 int getsum(int index)  //原序列中index位置之前小于等于array[index]的个数27 {28     int sum=0;29     while(index>0)30     {31         sum+=tree[index];32         index-=(-index)&index;33     }34     return sum;35 }36 37 bool cmp(struct node a,struct node b)38 {39     if(a.digit==b.digit)  //因为我离散化了，然后坐标里有重复的数字，因此需要在这里保存稳定性40         return a.number