POJ 2481 Cows (数组数组求逆序对)

给你n个区间，让你求每个区间被真包含的区间个数有多少，注意是真包含，所以要是两个区间的x y都相同就算0。(类似poj3067，cf652D)

对每个区间的x从小到大排序，相同的话按y从大到小排序。然后对枚举每个区间的y求其逆序对，然后在y的位置上置1。但是存在两个区间完全重合，我的做法比较搓，就是判断和前一个区间是否完全相同，要是相同，就把前一个答案赋值给这个。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 const int MAXN = 1e5 + 5;
 7 typedef long long LL;
 8 int bit[MAXN] , m , ans[MAXN];
 9 struct data {
10     int x , y , id;
11     bool operator <(const data &cmp) const {
12         if(x == cmp.x)
13             return y > cmp.y;
14         return x < cmp.x;
15     }
16 }a[MAXN];
17 
18 inline void add(int i) {
19     for( ; i <= m ; i += (i & -i))
20         bit[i]++;
21 }
22 
23 int sum(int i) {
24     int s = 0;
25     for( ; i >= 1 ; i -= (i & -i))
26         s += bit[i];
27     return s;
28 }
29 
30 int main()
31 {
32     int n;
33     while(~scanf("%d" , &n) && n) {
34         memset(bit , 0 , sizeof(bit));
35         m = 0;
36         for(int i = 0 ; i < n ; i++) {
37             scanf("%d %d" , &a[i].x , &a[i].y);
38             a[i].id = i;
39             a[i].x++ , a[i].y++;
40             m = max(m , a[i].y);
41         }
42         sort(a , a + n);
43         for(int i = 0 ; i < n ; i++) {
44             if(i > 0 && a[i].x == a[i - 1].x && a[i].y == a[i - 1].y) {
45                 ans[a[i].id] = ans[a[i - 1].id];                //判断相同并赋值
46             }
47             else { 
48                 ans[a[i].id] = i - sum(a[i].y - 1);
49             }
50             add(a[i].y);
51         }
52         for(int i = 0 ; i < n ; i++) {
53             if(i != n - 1)
54                 printf("%d " , ans[i]);
55             else
56                 printf("%d
" , ans[i]);
57         }
58     }
59 }