牛客小白月赛16 F 小石的妹子 （线段树）

链接：https://ac.nowcoder.com/acm/contest/949/F
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

小石有 n 个妹子，每个妹子都有一个细心程度 aiai 和一个热心程度 bibi，
小石想给她们一个重要程度 titi（重要程度为 1 表示最重要，重要程度越小表示越重要）。
如果一个妹子 i 的细心程度和热心程度都比妹子 j 大，那么妹子 i 的重要程度要大于妹子 j 的重要程度，即妹子 i 比妹子 j 重要。
流程如下：
每次从所有没有重要程度的妹子中，找到若干妹子。对于这些妹子的任意一个，需要保证没有其他妹子比她更重要。然后把她们的重要程度标为 1 。下一次再从剩下没有重要程度的妹子中找到若干妹子，依然符合上述条件，然后把她们的重要程度标为 2，……，重复直到所有妹子都有自己的重要程度。
由于妹子太多，小石忙不过来，请你帮帮他。

输入描述:

第一行输入一个正整数 n，表示妹子的数量。
接下来 n 行，每行两个正整数 ai,biai,bi，描述每个妹子的细心程度和热心程度。 
保证所有的 aiai 两两不等，所有的 bibi 两两不等。 

输出描述:

共 n 行，第 i 行输出一个正整数 titi 表示第 i 个妹子的重要程度。

示例1

输入

5

1 4

2 2

3 3

4 1

5 5

输出

2

3

2

2

1

说明

第一轮取第 5 个妹子（5 5），因为没有其他妹子比她重要，标记为 1；

第二轮取编号为 1，3，4 的妹子，因为对于其中的任意一个妹子，都没有其他妹子比她们重要，标记为 2；

第三轮把编号为 2 的妹子标记为 3 。

备注:

1≤n≤105,1≤ai,bi≤1091≤n≤105,1≤ai,bi≤109

解题思路：像那二维偏序问题，先对a，b数组进行离散化处理一下，然后再按b值从大到小排一下序，然后从前往后对于第i个妹子的等级为比她的a值大的妹子中等级最大值加1，然后再将这个妹子的等级更新到线段树中。
代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=1e5+;

int n;

struct node{

    int a,b;

    int id,rk;

}p[maxn];

int Max[maxn*];

bool cmp(node x,node y){

    return x.b>y.b;

}

bool cmp1(node x,node y){

    return x.a<y.a;

}

bool cmp2(node x,node y){

    return x.b<y.b;

}

bool cmp3(node x,node y){

    return x.id<y.id;

}

void pushup(int rt){

    Max[rt]=max(Max[rt<<],Max[rt<<|]);

}

void update(int pos,int val,int l,int r,int rt){

    if(l==r){

        Max[rt]=val;

        return;

    }

    int mid=(l+r)/;

    if(mid>=pos) update(pos,val,l,mid,rt<<);

    if(mid<pos) update(pos,val,mid+,r,rt<<|);

    pushup(rt);

}

int ask(int L,int R,int l,int r,int rt){

    if(L<=l&&R>=r)

        return Max[rt];

    int mid=(l+r)/;

    int ans=;

    if(L<=mid) ans=max(ans,ask(L,R,l,mid,rt<<));

    if(R>mid) ans=max(ans,ask(L,R,mid+,r,rt<<|));

    return ans;

}

int main(){

    scanf("%d",&n);

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

        scanf("%d%d",&p[i].a,&p[i].b);

        p[i].id=i;

    }

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

    for(int i=;i<=n;i++) p[i].a=i;

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

    for(int i=;i<=n;i++) p[i].b=i;

    sort(p+,p++n,cmp); //按b值从大到小排

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

        p[i].rk=ask(p[i].a,n,,n,)+;//查找大于当前妹子a值的等级最大值再加1

        update(p[i].a,p[i].rk,,n,); //将第i个妹子的等级更新到线段树中

    }

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

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

        printf("%d\n",p[i].rk);

    return ;

}