You are given n segments on a line. There are no ends of some segments that coincide. For each segment find the number of segments it contains.
Input The first line contains a single integer n (1 ≤ n ≤ 2·105) — the number of segments on a line.
Each of the next n lines contains two integers li and ri ( - 109 ≤ li < ri ≤ 109) — the coordinates of the left and the right ends of the i-th segment. It is guaranteed that there are no ends of some segments that coincide.
Output Print n lines. The j-th of them should contain the only integer aj — the number of segments contained in the j-th segment.
Example Input 4 1 8 2 3 4 7 5 6 Output 3 0 1 0 Input 3 3 4 1 5 2 6 Output 0 1 1
/* 树状数组，离散化 对于原始段，按照左端点从大到小排序，如果左端点相同，则按照右端点从小到大进行排序， 这样的话，对于段 i 来说，可能包括它的段就是 x ( x > i ) 段； 要求段 i 包含了多少段，那么可以将每个段的右端点赋值 1， 于是排好序后，对于每个段，统计下它右端点前的和，即为结果，然后更新 但是，右端点的值很大，所以用按从小到大对应一个小的值，也就是离散化； */ #include<bits/stdc++.h> using namespace std; const int maxn=200007*4; int sum[maxn]; struct node{ int x,y,id; }; node a[maxn]; int ans[maxn]; int n; int low_bit(int x) { return x&(-x); } int update(int x) { while(x<=n) { sum[x]++; x+=low_bit(x); } } int query(int x) { int ans=0; while(x>0) { ans+=sum[x]; x-=low_bit(x); } return ans; } int cmp(node a,node b) { return a.y < b.y; } int cmp1(node a,node b) { if(a.x != b.x ) return a.x > b.x; else return a.y < b.y; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d",&a[i].x,&a[i].y); a[i].id=i; } sort(a+1,a+1+n,cmp); for(int i=1;i<=n;i++) a[i].y=i; sort(a+1,a+1+n,cmp1); for(int i=1;i<=n;i++) { ans[a[i].id] = query(a[i].y); update(a[i].y); } for(int i=1;i<=n;i++) printf("%d\n",ans[i]); return 0; }