CodeForces 652D Nested Segments

离散化+树状数组

先对坐标离散化，把每条线段结尾所在点标1，

询问某条线段内有几条线段的时候，只需询问这段区间的和是多少，询问结束之后再把这条线段尾部所在点标为0

#include<cstdio>

#include<cstring>

#include<cmath>

#include<queue>

#include<algorithm>

using namespace std;

const int maxn=*1e5+;

struct X

{

    int x,y,ans,id;

}p[*maxn];

int n;

int lsh[*maxn],tot;

int c[*maxn];

bool cmp(const X&a,const X&b)

{

    return a.x<b.x;

}

bool cmp2(const X&a,const X&b)

{

    return a.id<b.id;

}

int lowbit(int x)

{

    return x&(-x);

}

void update(int pos,int val)

{

    while(pos<=*n)

    {

        c[pos]=c[pos]+val;

        pos=pos+lowbit(pos);

    }

}

int getsum(int pos)

{

    int res=;

    while(pos>)

    {

        res=res+c[pos];

        pos=pos-lowbit(pos);

    }

    return res;

}

int get(int num)

{

    int l=,r=tot-;

    while(l<=r)

    {

        int mid=(l+r)/;

        if(lsh[mid]<=num)

        {

            if(lsh[mid]==num) return mid+;

            else l=mid+;

        }

        else r=mid-;

    }

}

int main()

{

    scanf("%d",&n);

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

    {

        int li,ri; scanf("%d%d",&li,&ri);

        lsh[tot++]=li; lsh[tot++]=ri;

        p[i].x=li; p[i].y=ri; p[i].id=i;

    }

    sort(lsh,lsh+tot);

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

    {

        p[i].x=get(p[i].x);

        p[i].y=get(p[i].y);

    }

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

    memset(c,,sizeof c);

    for(int i=;i<=n;i++) update(p[i].y,);

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

    {

        if(p[i].x+>p[i].y-) p[i].ans=;

        else p[i].ans=getsum(p[i].y-)-getsum(p[i].x+);

        update(p[i].y,-);

    }

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

    for(int i=;i<=n;i++) printf("%d\n",p[i].ans);

    return ;

}