1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 5 using namespace std; 6 7 struct Node 8 { 9 int l,r; 10 int num; 11 }bn[16000000]; 12 13 void build(int k,int l,int r) 14 { 15 bn[k].l=l; 16 bn[k].r=r; 17 bn[k].num=0; 18 if(bn[k].l==bn[k].r) 19 return ; 20 int lk=k*2; 21 int rk=lk+1; 22 int mid=(l+r)/2; 23 build(lk,l,mid); 24 build(rk,mid+1,r); 25 } 26 27 void change(int k,int i) 28 { 29 if(bn[k].l==bn[k].r&&bn[k].r==i) 30 { 31 bn[k].num++; 32 return ; 33 } 34 int lk=k*2; 35 int rk=lk+1; 36 if(bn[lk].r>=i) 37 change(lk,i); 38 else if(bn[rk].l<=i) 39 change(rk,i); 40 bn[k].num=bn[lk].num+bn[rk].num; 41 } 42 43 int search(int k,int l,int r) 44 { 45 if(bn[k].l==l&&bn[k].r==r) 46 { 47 return bn[k].num; 48 } 49 int lk=k*2; 50 int rk=lk+1; 51 if(bn[lk].r<l) 52 return search(rk,l,r); 53 else if(bn[rk].l>r) 54 return search(lk,l,r); 55 else 56 return search(lk,l,bn[lk].r)+search(rk,bn[rk].l,r); 57 } 58 int count[1640100]; 59 int main() 60 { 61 int n; 62 while(scanf("%d",&n)!=EOF) 63 { 64 build(1,0,32010); 65 int a,b; 66 memset(count,0,sizeof(count)); 67 for(int i=0;i<n;i++) 68 { 69 scanf("%d%d",&a,&b); 70 count[search(1,0,a)]++; 71 change(1,a); 72 } 73 for(int i=0;i<n;i++) 74 cout<<count[i]<<endl; 75 } 76 return 0; 77 }