即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

Nested Segments CodeForces – 652D (树状数组,离散化)

编程语言 zhuanshunzhe 15℃ 0评论

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

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;
}

转载请注明:CodingBlog » Nested Segments CodeForces – 652D (树状数组,离散化)

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情