Cows POJ

Cows

思路：我们可以按照每个范围的S从小到大排序，相同的S按E从大到小排序，这样的好处是当前范围的S一定大于等于之前范围的S（即当前的范围可能被之前范围的包围），那么我们只需要统计之前的范围E比当前的范围E大于等于的有几个即可。这里需要注意如果两个范围完全相同的情况，我们可以把当前的范围与之前的范围比较，如果相同，直接把之前的答案复制到当前就可。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <queue>
 4 #include <algorithm>
 5 
 6 #define lson (rt << 1)
 7 #define rson ((rt << 1 | 1)
 8 #define ll long long
 9 #define pb push_back
10 
11 using namespace std;
12 
13 const int N = 1e5 + 10;
14 struct node{
15     int number, l ,r;
16     bool friend operator<(const node& a, const node & b){
17         if(a.l != b.l) return a.l < b.l;
18         else return a.r > b.r;
19     }
20 }a;
21 vector<node > vn;
22 int tot[N], c[N], Max;
23 int n;
24 
25 inline int lb(int x){
26     return x&(-x);
27 }
28 
29 void add(int x){
30     for(int i = x; i <= Max; i += lb(i)) ++c[i];
31 }
32 
33 int sum(int x){
34     int sum = 0;
35     for(int i = x; i >= 1; i -= lb(i)) sum += c[i];
36     return sum;
37 }
38 
39 void solve(){
40 
41     while(scanf("%d", &n) && n){
42         vn.clear();
43         Max = 0;
44         for(int i = 1; i <= n; ++i){
45             a.number = i;
46             scanf("%d%d", &a.l, &a.r);
47             ++a.l; ++a.r;
48             Max = max(Max, a.r);
49             vn.pb(a);
50         }
51         sort(vn.begin(), vn.end());
52         for(int i = 1; i <= n; ++i) tot[i] = 0;
53         for(int i = 1; i <= Max; ++i) c[i] = 0;
54         int pre_l = -1, pre_r = -1, inx = -1;
55         for(int i = 0; i != vn.size(); ++i){
56             node it = vn[i];
57             if(it.l == pre_l && it.r == pre_r){ //范围相同
58                 tot[it.number] = tot[inx];
59                 add(it.r);
60             }
61             else{
62                 pre_l = it.l; pre_r = it.r; inx = it.number; //改变前一个点
63                 if(it.r - 1 == 0) tot[it.number] = sum(Max);
64                 else tot[it.number] = sum(Max) - sum(it.r - 1);
65                 add(it.r);
66             }
67         }
68         printf("%d", tot[1]);
69         for(int i = 2; i <= n; ++i) printf(" %d", tot[i]);
70         printf("
");
71     }
72 }
73 
74 
75 int main(){
76 
77 
78 
79     solve();
80 
81 
82     return 0;
83 }