POJ 2481 Cows 【树状数组】

题目大意：

就是给出N个区间，问这个区间是多少个区间的真子集。

解题分析：

本题与stars类似，只要巧妙的将线段的起点和终点分别看成二维坐标系中的x,y坐标，就会发现，其实本题就是求每个点(把线段看成点) 左上角点的个数(包括边界，但并不包括与该点坐标完全相同的点)，所以，与stars类似，对所有线段先进行排序，按 y坐标由大到小排序，若左边相同，就对x坐标进行从小到大排序。然后就可以直接对每个点的x坐标建立一维树状数组求解了。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 typedef long long ll;
 7 const int M =1e5+10;
 8 int n;
 9 int tr[M],ans[M];
10 struct Seg{
11     int s,e,loc;
12     bool operator < (const Seg &tmp)const{
13         if(e==tmp.e)return s<tmp.s;   //对于终点相同的线段，起点从小到大排序
14         else return e>tmp.e;     //因为要求得该点左上角的点的数量，所以是将终点按从大到小排序
15     }
16 }seg[M];
17 int lowbit(int x){return x&(-x);}
18 void add(int i,int val){
19     while(i<=n){
20         tr[i]+=val;
21         i+=lowbit(i);
22     }
23 }
24 int sum(int i){
25     int ans=0;
26     while(i>0){
27         ans+=tr[i];
28         i-=lowbit(i);
29     }
30     return ans;
31 }
32 int main(){
33     while(scanf("%d",&n)!=EOF,n){
34         for(int i=1;i<=n;i++){
35             scanf("%d%d",&seg[i].s,&seg[i].e);
36             seg[i].loc=i;
37         }
38         sort(seg+1,seg+n+1);
39         memset(tr,0,sizeof(tr));
40         memset(ans,0,sizeof(ans));
41         for(int i=1;i<=n;i++){
42             if(i!=1&&seg[i].s==seg[i-1].s&&seg[i].e==seg[i-1].e)    //因为题目要求的是每个线段的真子集，所以这里对于那些完全相等的线段要进行特殊处理
43                 ans[seg[i].loc]=ans[seg[i-1].loc];
44             else
45                 ans[seg[i].loc]=sum(seg[i].s+1);  //求出起点小于等于当前线段起点的线段个数，因为那些线段的终点比当前线段大，所以此时求的就是完全包含当前线段的线段个数
46             add(seg[i].s+1,1);
47         }
48         for(int i=1;i<=n;i++){
49             i==n?printf("%d
",ans[i]):printf("%d ",ans[i]);
50         }
51     }
52     return 0;
53 }

2018-10-17