POJ 2481 - Cows

题目描述

Cows

题目描述

$S_i<=S_{j}and{E}_j<=E_{i}and{E}_i?S_i>E_j?S_j$ 表示牛 $i$ 比牛 $j$ 壮，翻译一下就是：

那这样子就很好处理了，我们希望 $E$ 越大 $S$ 越小。于是，我们先按照 $E$ 从大到小排列一遍，这样就可以保证后面处理时拿到的 $E_i$ 都大于其后面的元素。对于 $E_i=E_j$，下一步我们希望的是$S_i<S_j$，这个很好用树状数组解决，$sum(S_i)$就可以求得比 $S_i$ 更小的元素个数，也就得到了比当前更壮的牛的数目。

#include <iostream>
#include <algorithm>
#include <string.h>using namespace std;int c[100010], cnt[100010];
int n, x, y, mmax;struct cow{
    int s, e;int id;
}cows[100010];bool cmp(const cow& a, const cow& b){
    if(a.e==b.e) return a.s<b.s;return a.e>b.e;
}int lowbit(int x){
    return x&(-x);}void add(int x){
    for(int i=x;i<=n;i+=lowbit(i))c[i] += 1;
}int sum(int x){
    int s = 0;for(int i=x;i;i-=lowbit(i))s += c[i];return s;
}int main()
{
    while(scanf("%d", &n) && n){
    mmax = 0;memset(c, 0, sizeof(c));for(int i=1;i<=n;i++){
    scanf("%d%d", &x, &y);cows[i].s = x+1; cows[i].e = y+1;cows[i].id = i;if(cows[i].e>mmax) mmax = cows[i].e;}sort(cows+1, cows+1+n, cmp);for(int i=1;i<=n;i++){
    if(i>1 && cows[i].s==cows[i-1].s && cows[i].e==cows[i-1].e)cnt[cows[i].id] = cnt[cows[i-1].id];else cnt[cows[i].id] = sum(cows[i].s);add(cows[i].s);}for(int i=1;i<=n;i++){
    if(i!=1) printf(" ");printf("%d", cnt[i]);}printf("\n");}return 0;
}