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
4
1 8
2 3
4 7
5 6
3
0
1
0
3
3 4
1 5
2 6
0
1
1
题意：现在X轴上，有N个线段，给出每条线段是左端点和右端点，求每条线段覆盖了多少其他的线段。
思路：按右端点排序，然后一条一条的纳入考虑。每考虑一条新的，查询之前考虑过的左端点大于当前左端点的，就是当前线段的答案。然后把当前线段的左端点插入树状数组。（因为右端点是有序的，只需要考虑左端点即可，而左端点只需要树状数组来维护区间和及查询）。
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=;
int sum[maxn],a[maxn],ans[maxn],N,tot;
struct in
{
int x; int y; int id;
friend bool operator <(in a,in b){
if(a.y==b.y) return a.x>b.x; return a.y<b.y;
}
}s[maxn];
void add(int x){
while(x<=tot) {
sum[x]++;
x+=(-x)&x;
}
}
int query(int x){
int res=;
while(x){
res+=sum[x];
x-=(-x)&x;
} return res;
}
int main()
{
scanf("%d",&N);
for(int i=;i<=N;i++) {
scanf("%d%d",&s[i].x,&s[i].y);
s[i].id=i;
a[++tot]=s[i].x; a[++tot]=s[i].y;
}
sort(a+,a+tot+);
tot=unique(a+,a+tot+)-(a+);
sort(s+,s+N+);
for(int i=;i<=N;i++){
int tx=lower_bound(a+,a+tot+,s[i].x)-a;
int ty=lower_bound(a+,a+tot+,s[i].y)-a;
ans[s[i].id]=query(ty)-query(tx-);
add(tx);
}
for(int i=;i<=N;i++) printf("%d\n",ans[i]);
return ;
}