1 # include <cstdio>
2 # include <cstring>
3 # include <algorithm>
4 using namespace std;
5
6 # define B 100005
7 # define N 100005
8
9 struct Intv {int s, e;};
10
11 Intv c[N];
12 int n, a[B], r[N], le[N];
13
14 bool cmp(const int x, const int y)
15 {
16 if (c[x].s == c[y].s) return c[x].e > c[y].e;
17 return c[x].s < c[y].s;
18 }
19 /**************************************************/
20 int getsum(int x)
21 {
22 int ret = 0;
23 while (x > 0) ret += a[x], x -= x&(-x);
24 return ret;
25 }
26 void inc(int x)
27 {
28 while (x <= B) ++a[x], x += x&(-x);
29 }
30 /**************************************************/
31 int main()
32 {
33 int i, n, x;
34
35 while (scanf("%d", &n), n)
36 {
37 memset(a, 0, sizeof(a));
38 for (i = 0; i < n; ++i)
39 r[i] = i, scanf("%d%d", &c[i].s, &c[i].e);
40 sort(r, r+n, cmp);
41 for (i = 0; i < n; ++i)
42 {
43 x = c[r[i]].e + 1, inc(x);
44 if (i && c[r[i]].e==c[r[i-1]].e && c[r[i]].s==c[r[i-1]].s)
45 le[r[i]] = le[r[i-1]];
46 else
47 le[r[i]] = i-getsum(x-1);
48 }
49 for (i = 0; i < n; ++i)
50 {
51 if (i) putchar(' ');
52 printf("%d", le[i]);
53 }
54 putchar('\n');
55 }
56
57 return 0;
58 }
59
posted on 2012-09-02 11:51
yajunw 阅读(126)
评论(0) 编辑 收藏 引用