D. Nested Segments

题目连接：

http://www.codeforces.com/contest/652/problem/D

Description

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.

Sample Input

4

1 8

2 3

4 7

5 6

Sample Output

3

0

1

0

Hint

题意

给你n个线段，让你输出每个线段完全包含多少个其他的线段

保证任意两个线段的端点不重合

题解：

先离散化一波

然后离线树状数组维护一波就好了

for循环暴力扫左端点，然后树状数组去查询小于右端点的线段有多少个，就完了

代码

#include<bits/stdc++.h>

using namespace std;

const int maxn = 4e5+7;

pair<pair<int,int>,int>p[maxn];

int ans[maxn];

vector<int> Q;

map<int,int> H;

int a[maxn];

int lowbit(int x){return x&(-x);}

void update(int x,int v)

{

    for(int i=x;i<maxn;i+=lowbit(i))

        a[i]+=v;

}

int get(int x)

{

    int tot = 0;

    for(int i=x;i;i-=lowbit(i))

        tot+=a[i];

    return tot;

}

int main()

{

    int n;

    scanf("%d",&n);

    for(int i=1;i<=n;i++)

    {

        scanf("%d%d",&p[i].first.first,&p[i].first.second);

        Q.push_back(p[i].first.first),Q.push_back(p[i].first.second);

        p[i].second=i;

    }

    sort(Q.begin(),Q.end());

    Q.erase(unique(Q.begin(),Q.end()),Q.end());

    for(int i=0;i<Q.size();i++)

        H[Q[i]]=i+1;

    for(int i=1;i<=n;i++)

    {

        p[i].first.first=H[p[i].first.first];

        p[i].first.second=H[p[i].first.second];

        update(p[i].first.second,1);

    }

    sort(p+1,p+1+n);

    for(int i=1,j=1;i<maxn;i++)

    {

        while(j<=n&&p[j].first.first==i)

        {

            ans[p[j].second]=get(p[j].first.second);

            update(p[j].first.second,-1);

            j++;

        }

        if(j==n+1)break;

    }

    for(int i=1;i<=n;i++)

        printf("%d\n",ans[i]-1);

}