Educational Codeforces Round 10 D. Nested Segments

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

D. Nested Segments

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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 l i and r i ( - 109 ≤ l i < r i ≤ 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 a j — the number of segments contained in the j -th segment.

Examples

input

output

input

output

0
1
1

离散化+ 线段树或树状数组维护前缀和

想按照左端点进行排序，然后逆序对右端点进行查询,插入.这样可以保证线段的包含关系。写的有点挫，一开始始终re后来把线段树开到8*maxn就过了。。

/* ***********************************************

Author        :guanjun

Created Time  :2016/3/28 15:34:10

File Name     :cfedu10d.cpp

************************************************ */

#include <iostream>

#include <cstring>

#include <cstdlib>

#include <stdio.h>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <iomanip>

#include <list>

#include <deque>

#include <stack>

#define ull unsigned long long

#define ll long long

#define mod 90001

#define INF 0x3f3f3f3f

#define maxn 211000

#define cle(a) memset(a,0,sizeof(a))

const ull inf = 1LL << ;

const double eps=1e-;

using namespace std;

struct Node{

    int x,y;

    int id;

}Nod[maxn];

bool cmp(Node a,Node b){

    return a.x<b.x;

}

struct node{

    int l,r;

    ll sum;

    int c;

}nod[maxn*];

int ans[maxn];

void push_up(int i){

    nod[i].sum=nod[i<<].sum+nod[i<<|].sum;

}

void build(int i,int l,int r){

    nod[i].l=l;

    nod[i].r=r;

    nod[i].c=;

    if(l==r){

        nod[i].sum=;

        return ;

    }

    int mid=(l+r)/;

    build(i<<,l,mid);

    build(i<<|,mid+,r);

    push_up(i);

}

void update(int i,int k,int x){

    if(nod[i].l==k&&nod[i].r==k){

        nod[i].sum+=x;

        return ;

    }

    int mid=(nod[i].l+nod[i].r)/;

    if(k<=mid)update(i<<,k,x);

    else update(i<<|,k,x);

    push_up(i);

}

ll quary(int i,int l,int r){

    if(nod[i].l==l&&nod[i].r==r){

        return nod[i].sum;

    }

    int mid=(nod[i].l+nod[i].r)/;

    ll ans=;

    if(r<=mid)ans+=quary(i<<,l,r);

    else if(l>mid)ans+=quary(i<<|,l,r);

    else {

        ans+=quary(i<<,l,mid);

        ans+=quary(i<<|,mid+,r);

    }

    push_up(i);

    return ans;

}

int num[*maxn];

map<int,int>mp;

int main()

{

    #ifndef ONLINE_JUDGE

    freopen("in.txt","r",stdin);

    #endif

    //freopen("out.txt","w",stdout);

    int n,q;

    ll z;

    while(cin>>n){

        mp.clear();

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

            scanf("%d%d",&Nod[i].x,&Nod[i].y);

            num[i]=Nod[i].x;

            num[i+n]=Nod[i].y;

            Nod[i].id=i;

        }

        sort(num+,num++(*n));

        int cnt=;

        for(int i=;i<=*n;i++){

            mp[num[i]]=cnt;

            cnt++;

        }

        build(,,mp[num[*n]]);

        sort(Nod+,Nod++n,cmp);

        for(int i=n;i>=;i--){

            ans[Nod[i].id]=quary(,,mp[Nod[i].y]);

            update(,mp[Nod[i].y],);

        }

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

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

        }

    }

    return ;

}