Cows

 1 #include <cstdio>
 2 #include <cstring>
 3 #include<algorithm>
 4 #include<map>
 5 #include<stack>
 6 #include<cmath>
 7 typedef long long ll;
 8 using namespace std;
 9 const int MAXN=1e6+10;
10 int  m,n;
11 struct node
12 {
13     int  left;
14     int right;
15     int num;
16 } str[MAXN];
17 int ans[MAXN]={0};
18 bool cmp(node a,node b)//排序预处理
19 {
20     if(a.right==b.right)
21         return a.left<b.left;
22     return a.right>b.right;
23 }
24 int Lowbit(int  x)
25 {
26     return x&(-x);
27 }
28 void update(int  i, int x,int c[])
29 {
30     while(i <=n)
31     {
32         c[i] += x;
33         i += Lowbit(i);
34     }
35 }
36 int  Getsum(int x,int c[])
37 {
38     int sum=0;
39     while(x>0)
40     {
41         sum+=c[x];
42         x-=Lowbit(x);
43     }
44     return sum;
45 }
46 int main()
47 {
48     int T,k,flag=0;
49     while(scanf("%d",&n)!=-1&&n)
50     {
51         flag++;
52         int c[MAXN]= {0};
53         int a[MAXN]={0};
54         ll kk=0;
55         for(int i=1; i<=n; i++)
56         {
57             scanf("%d%d",&str[i].left,&str[i].right);
58             str[i].num=i;
59         }
60         sort(str+1,str+n+1,cmp);
61         ans[str[1].num]=0;
62         update(str[1].left+1,1,c);
63         for(int i=2; i<=n; i++)
64         {
65             if(str[i].left==str[i-1].left&&str[i].right==str[i-1].right)//判断该区间的右端点与上一个区间的右端点的大小
66             {
67                ans[str[i].num]=ans[str[i-1].num];
68             }
69             else
70             {
71                 ans[str[i].num]=Getsum(str[i].left+1,c);
72             }
73             update(str[i].left+1,1,c);
74         }
75         for(int i=1;i<=n;i++)
76         {
77             printf("%d%c",ans[i],i==n?‘\n‘:‘ ‘);
78         }
79 
80     }
81 
82     return 0;
83 }