Cows POJ - 2481

 

点击打开链接

离线处理 先将左右端点排序 若对右端点排序则用左端点进行线段树更新查询

 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

struct node1
{
    int l;
    int r;
    int id;
    int ans;
};

struct node2
{
    int l;
    int r;
    int val;
};

node1 pre[100010];
node2 tree[400010];
int n;

bool cmpI(node1 n1,node1 n2)
{
    if(n1.r==n2.r)
    {
        return n1.l>n2.l;
    }
    else
    {
        return n1.r<n2.r;
    }
}

bool cmpII(node1 n1,node1 n2)
{
    return n1.id<n2.id;
}

void build(int l,int r,int cur)
{
    int m;
    tree[cur].l=l;
    tree[cur].r=r;
    tree[cur].val=0;
    if(l==r) return;
    m=(l+r)/2;
    build(l,m,cur*2);
    build(m+1,r,cur*2+1);
    return;
}

void pushup(int cur)
{
    tree[cur].val=tree[cur*2].val+tree[cur*2+1].val;
    return;
}

int query(int pl,int pr,int cur)
{
    int res;
    if(pl<=tree[cur].l&&tree[cur].r<=pr)
    {
        return tree[cur].val;
    }
    res=0;
    if(pl<=tree[cur*2].r) res+=query(pl,pr,cur*2);
    if(pr>=tree[cur*2+1].l) res+=query(pl,pr,cur*2+1);
    return res;
}

void update(int tar,int cur)
{
    if(tree[cur].l==tree[cur].r)
    {
        tree[cur].val++;
        return;
    }
    if(tar<=tree[cur*2].r) update(tar,cur*2);
    else update(tar,cur*2+1);
    pushup(cur);
    return;
}

int main()
{
    int i,maxx;
    while(scanf("%d",&n)!=EOF)
    {
        if(n==0) break;
        maxx=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d%d",&pre[i].l,&pre[i].r);
            pre[i].id=i,pre[i].ans=0;
            maxx=max(maxx,pre[i].r);
        }
        build(0,maxx,1);
        sort(pre+1,pre+n+1,cmpI);
        for(i=n;i>=1;i--)
        {
            if(i!=n&&pre[i].l==pre[i+1].l&&pre[i].r==pre[i+1].r)
            {
                pre[i].ans=pre[i+1].ans-1;
            }
        }
        for(i=n;i>=1;i--)
        {
            pre[i].ans+=query(0,pre[i].l,1);
            update(pre[i].l,1);
        }
        sort(pre+1,pre+n+1,cmpII);
        for(i=1;i<n;i++)
        {
            printf("%d ",pre[i].ans);
        }
        printf("%d\n",pre[i].ans);
    }
    return 0;
}