POJ2481 Cows（树状数组）

题目链接

题意：n 个牛，每个牛在一条数轴上控制的范围是[a, b]，如果牛 1 控制的范围完全包括了牛 2（除了范围完全相等的情况），那么称牛 1 比牛 2 强壮。给出 n 个牛控制的范围，按照顺序输出每个牛比几个牛强壮。

典型的树状数组题，由于 sum 函数只能控制一个因子，所以我们按照每个牛的右端点从大到小排序（相等时按照左端点从小到大），用前缀和解决左端点就可以了。需要注意的是要讨论一下两个牛的控制范围完全相等的情况。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<string>
using namespace std;
int n, q;
int a[100005];
int b[100005];
struct node{
    int x, y, id;
}N[100005];

bool cmp(node a, node b){
    if(a.y == b.y) return a.x < b.x;
    else return a.y > b.y;
}

int lowbit(int x){
    return x&(-x);
}

void add(int pos, int num){
    while(pos <= n){
        a[pos] += num;
        pos += lowbit(pos);
    }
}

int sum(int n){
    int sum = 0;
    while(n > 0){
        sum += a[n];
        n -= lowbit(n);
    }
    return sum;
}

int main(){
    //freopen("a.txt", "r", stdin);
    while(~scanf("%d", &q) && q){
        memset(a, 0, sizeof(a));
        n = 0;
        for(int i = 1; i <= q; i++){
            int a, b;
            scanf("%d %d", &a, &b);
            N[i].id = i;
            N[i].x = a+1;
            N[i].y = b+1;
            n = max(n, N[i].y);
        }
        sort(N+1, N+1+q, cmp);
        //for(int i = 1; i <= q; i++)
            //cout << N[i].id << " " << N[i].x << " " << N[i].y << endl;
        N[0].x = -1;
        N[0].y = -1;
        for(int i = 1; i <= q; i++){
            if(N[i-1].x == N[i].x && N[i-1].y == N[i].y){
                add(N[i].x, 1);
                b[N[i].id] = b[N[i-1].id];
            }
            else{
                b[N[i].id] = sum(N[i].x);
                add(N[i].x, 1);
            }
        }
        for(int i = 1; i <= q; i++){
            cout << b[i];
            if(i != q) cout << " ";
        }
        cout << endl;
    }
    return 0;
}