poj2481

题意：给定一些线段(s, e),起点为s，终点为e，求每一段线段被多少线段包含（不包括相等）

思路：很明显的树状数组题目。。但是做的时候想了挺久。。（下面的x为线段起点， y为线段终点）

做法1：先对线段进行排序，比较函数为 a.x < b.x || a.x == b.x && a.y > b.y;

接下来便依次插入树状数组中，插的时候左端点 +1，右端点-1，这样求和时前面的线段自然消掉

统计是算sum(a[i].y)即可。。

但是这样我们发现落下了一种情况，就是把 x < a[i].x && y == a[i].y情况给消掉了，所以还要排序在统计一遍。。

这种做法我写完2300+ms过了。。

做法2：差不多的思路，但是结合把(x, y)当成二维坐标，这样我们发现其实上就是求其左上方的点有多少个。。采用poj2352stars做法即可。。需要判重。。

以为会快很多，。。没想到也要2200+ms才过。。

法1：

  1 /*
  2  * author:  yzcstc
  3  * Created Time:  2013骞?9鏈?7鏃?鏄熸湡鍏?12鏃?7鍒?1绉?
  4  * File Name: poj2481.cpp
  5  */
  6 #include<iostream>
  7 #include<sstream>
  8 #include<vector>
  9 #include<list>
 10 #include<deque>
 11 #include<queue>
 12 #include<stack>
 13 #include<map>
 14 #include<set>
 15 #include<algorithm>
 16 #include<cstdio>
 17 #include<cstdlib>
 18 #include<cstring>
 19 #include<cctype>
 20 #include<cmath>
 21 #define MXN 100010
 22 #define MXM 1000000
 23 #define M0(a) memset(a, 0, sizeof(a))
 24 #define eps 1e-8
 25 #define Inf 0x7fffffff
 26 using namespace std;
 27 struct oo{  
 28     int x, y, id; 
 29     bool operator <(const oo & b) const{
 30           return x < b.x || x == b.x && y > b.y;  
 31     }
 32 };
 33 oo a[240000];
 34 int cnt[240000], n, ans[101010];
 35 
 36 int lowbit(int x){
 37     return x & (-x) ;
 38 }
 39 
 40 void updata(int x, int v){
 41     while (x <= MXN){
 42          cnt[x] += v;
 43          x += lowbit(x);
 44     }
 45 }
 46 
 47 int get_sum(int x){
 48     int ret = 0;
 49     while (x){
 50         ret += cnt[x];
 51         x -= lowbit(x);
 52     }
 53     return ret;
 54 }
 55 
 56 bool cmp(const oo &a, const oo &b){
 57      if (a.y < b.y) return true;
 58      if (a.y == b.y && a.x < b.x) return true;
 59      return false;
 60 }
 61 
 62 void solve(){
 63     M0(cnt);
 64     M0(ans);
 65     for (int i = 1; i <= n; ++i){
 66         scanf("%d%d", &a[i].x, &a[i].y);
 67         ++ a[i].x;
 68         ++ a[i].y;
 69         a[i].id = i;
 70     }
 71     sort(a + 1, a + n + 1);
 72     int sum = 0;
 73     for (int i = 1; i <= n; ++i){
 74        ans[a[i].id] = get_sum(a[i].y);
 75        updata(a[i].x, 1); 
 76        updata(a[i].y, -1);
 77     }
 78     sort(a + 1, a + n + 1, cmp);
 79     int l = 1, r = 1;
 80     for (int i = 2; i <= n; ++i){
 81         while (l < i && a[l].y < a[i].y) ++l;
 82         r = max(r, l);
 83         while (r < i && a[r + 1].x < a[i].x) ++r;
 84         if (a[r].x == a[i].x) r = i;
 85         if (r < i) ans[a[i].id] +=  (r - l + 1);
 86     }
 87     for (int i = 1; i < n; ++i)
 88          printf("%d ", ans[i]);
 89     printf("%d
", ans[n]);
 90 }
 91 
 92 int main(){
 93     freopen("a.in","r",stdin);
 94     freopen("a.out","w",stdout);
 95     while (scanf("%d", &n) != EOF && n){
 96         solve();
 97     }
 98     fclose(stdin);  fclose(stdout);
 99     return 0;
100 }

法2：

 1 /*
 2  * author:  yzcstc
 3  * Created Time:  2013骞?9鏈?7鏃?鏄熸湡鍏?12鏃?7鍒?1绉?
 4  * File Name: poj2481.cpp
 5  */
 6 #include<iostream>
 7 #include<sstream>
 8 #include<vector>
 9 #include<list>
10 #include<deque>
11 #include<queue>
12 #include<stack>
13 #include<map>
14 #include<set>
15 #include<algorithm>
16 #include<cstdio>
17 #include<cstdlib>
18 #include<cstring>
19 #include<cctype>
20 #include<cmath>
21 #define MXN 100010
22 #define MXM 1000000
23 #define M0(a) memset(a, 0, sizeof(a))
24 #define eps 1e-8
25 #define Inf 0x7fffffff
26 using namespace std;
27 struct oo{  
28     int x, y, id; 
29     bool operator <(const oo & b) const{
30           return x < b.x || x == b.x && y > b.y;  
31     }
32     bool operator ==(const oo & b) const{
33           return x == b.x && y == b.y;  
34     }
35 };
36 oo a[240000];
37 int cnt[240000], n, ans[101010];
38 
39 int lowbit(int x){
40     return x & (-x) ;
41 }
42 
43 void updata(int x, int v){
44     while (x <= MXN){
45          cnt[x] += v;
46          x += lowbit(x);
47     }
48 }
49 
50 int get_sum(int x){
51     int ret = 0;
52     while (x){
53         ret += cnt[x];
54         x -= lowbit(x);
55     }
56     return ret;
57 }
58 
59 void solve(){
60     M0(cnt);
61     M0(ans);
62     for (int i = 1; i <= n; ++i){
63         scanf("%d%d", &a[i].x, &a[i].y);
64         ++ a[i].x;
65         ++ a[i].y;
66         a[i].id = i;
67     }
68     sort(a + 1, a + n + 1);
69     for (int i = 1; i <= n; ++i){
70        ans[a[i].id] = get_sum(MXN) - get_sum(a[i].y - 1);
71        updata(a[i].y, 1);
72     }
73     int l = 1;
74     for (int i = 2; i <= n; ++i){
75        while (l < i){
76              if (a[l] == a[i])  break;
77              ++l;
78        }
79        ans[a[i].id] -= (i - l);    
80     }
81     for (int i = 1; i < n; ++i)
82          printf("%d ", ans[i]);
83     printf("%d
", ans[n]);
84 }
85 
86 int main(){
87     freopen("a.in","r",stdin);
88     freopen("a.out","w",stdout);
89     while (scanf("%d", &n) != EOF && n){
90         solve();
91     }
92     fclose(stdin);  fclose(stdout);
93     return 0;
94 }