题目传送门
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAX_N = + ;
int cnt[MAX_N];
int ans[MAX_N];
int maxn = -;
struct node
{
int s, e;
int id;
}cow[MAX_N];
inline int read(void)
{
int x = , f = ; char ch = getchar ();
while (ch < '' || ch > '') {if (ch == '-') f = -; ch = getchar ();}
while (ch >= '' && ch <= '') {x = x * + ch - ''; ch = getchar ();}
return x * f;
}
inline void print(int x)
{
if (x < ) {putchar ('-'); x = -x;}
if (x > ) print (x / );
putchar (x % + '');
}
bool cmp(node x, node y) //先对e从大到小排序
{
if (x.e == y.e)
return x.s < y.s; //如果如果相等，再按s从小到大排序
else
return x.e > y.e;
}
int lowbit(int t) //求 2^t
{
//return t & (t ^ (t - 1));
return t & (-t);
}
void plus(int x)
{
while (x <= maxn)
{
ans[x]++; //记录强壮的牛数
x += lowbit (x);
}
}
int sum(int x) //统计前x项强壮的牛数
{
int sum = ;
while (x > )
{
sum += ans[x];
x -= lowbit(x);
}
return sum;
}
int main(void) //POJ 2481 Cows
{
//freopen ("inH.txt", "r", stdin);
int n;
while (scanf ("%d", &n) && n)
{
for (int i=; i<=n; ++i)
{
cow[i].s = read (); cow[i].e = read (); //读入外挂优化
//scanf ("%d%d", &cow[i].s, &cow[i].e);
cow[i].id = i;
maxn = max (maxn, cow[i].e);
}
memset (ans, , sizeof (ans));
sort (cow+, cow+n+, cmp);
for (int i=; i<=n; ++i)
{
if (cow[i].e == cow[i-].e && cow[i].s == cow[i-].s) //如果值相等，不加入统计
cnt[cow[i].id] = cnt[cow[i-].id];
else
{
cnt[cow[i].id] = sum (cow[i].s + ); //第id的牛有多少比它强壮
}
plus (cow[i].s + );
}
int j;
for (j=; j<n; ++j)
{
print (cnt[j]); putchar (' '); //输出外挂优化
//printf ("%d ", cnt[j]);
}
printf ("%d\n", cnt[j]);
}
return ;
}