POJ - 2481 Cows

题目链接：https://vjudge.net/problem/POJ-2481

题目大意

在x轴上有很多的线段，问每一个线段是多少个线段的真子集。

思路

我们可以考虑通过排序，让线段的左端点是从左到右的关系排列，每遍历到一个线段的时候，就看之前有多少个右端点是在[r,最大值]这就是答案，如果线段重叠，答案之前继承一下就可以了。

代码

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <stack>
#include <deque>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define PI acos(-1)
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;

int N;
struct node
{
    int l,r,id;
    bool operator < (const node &o) const{
        if(l != o.l) return l < o.l;
        else return r > o.r;
    }
}lr[maxn];
int tr[100010];
int ans[maxn];

inline void read(int &x){
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    x = s*w;
}
int lowbit(int x){
    return x&-x;
}
void add(int idx,int v){
    for(int i = idx;i<=100001;i += lowbit(i)) tr[i] += v;
}

int query(int r){
    int sum = 0;
    for(int i = r;i>=1;i -= lowbit(i)) sum += tr[i];
    return sum;
}
void solve(){
    sort(lr+1,lr+N+1);
    for(int i = 1;i<=N;i++){
        if(lr[i].l == lr[i-1].l && lr[i].r == lr[i-1].r){
            ans[lr[i].id] = ans[lr[i-1].id];
        }else ans[lr[i].id] = query(100001) - query(lr[i].r-1);
        add(lr[i].r,+1);
    }
}

int main(){
    while(cin>>N){
        if(N == 0) break;
        memset(tr,0,4*N+10);
        memset(ans,0,4*N+10);
        for(int i = 1;i<=N;i++){
            int l,r;read(l),read(r);l++,r++;
            lr[i] = {l,r,i};
        }
        solve();
        for(int i = 1;i<=N;i++) printf("%d ",ans[i]);
        puts("");
    }    
    return 0;
}