题目链接

description：

有n个妹子 分别有a,b值 只有a,b值均大于其他人才能设定为一个阶级的重要程度（具体看题目样例） 列出所有妹子的重要程度

solution：

二维点数问题.想到树状数组，我们只关心他们之间的相对大小，对于维度x采用离散化，然后对维度y降序排序，用树状数组维护当前重要程度最大值，对于每个人按照维度x更新和查询，查询出来的值 +1 是用来区分不同重要程度，选择对应下标存入res数组最后输出

code：

#include <bits/stdc++.h>

using namespace std;

struct node{
    int x,y;
    int id;
};

const int N = 1e5 + 50;
node a[N];
int res[N],t[N];

bool cmp(node a,node b){
    return a.y > b.y;
}

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

void update(int i,int v){
    for(;i > 0;i -= lowbit(i)){
        t[i] = max(t[i],v);
    }
}

int query(int i){
    int res = 0;
    for(;i < N;i += lowbit(i)){
        res = max(res,t[i]);
    }
    return res;
}

int main(){
    ios::sync_with_stdio(0);

    int n ;cin >> n;

    vector<int> v;

    for(int i = 1;i <= n;i ++){
        cin >> a[i].x >> a[i].y;
        a[i].id = i;
        v.push_back(a[i].x);
    }

    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());

    for(int i = 1;i <= n;i ++){
        a[i].x = lower_bound(v.begin(),v.end(),a[i].x) - v.begin() + 1;
    }

    sort(a + 1,a + 1 + n,cmp);

    for(int i = 1;i <= n;i ++){
        int now = query(a[i].x);
        res[a[i].id] = now + 1;
        update(a[i].x,now + 1);
    }

    for(int i = 1;i <= n;i ++){
        cout << res[i] << '\n';
    }

    return 0;
}