题解 | #小石的妹子#

思路：
线段树
先对ai进行排序
对于排序后的第 i 个妹子，她的排名就是 max{rk[j]}+1 (其中bj必须大于bi)，
之后对于bi我们先去离散化后开个线段树
让bi作为位置，重要程度ti作为树中的值
我们就找从bi到n位置中最大的ti是多少
找到后返回的值就是这个人的重要程度
（就是开个线段树找比b大的数的p[i]是多少）

AC代码：

#include <iostream>
#include <vector>
#include <algorithm>
#define mid (l+r>>1)
using namespace std;
const int N=1e5+10;
struct node{
     int a,b,i;
}a[N];
int tree[N<<2];
int res[N];
vector<int>v;
int getid(int x){return lower_bound(v.begin(),v.end(),x)-v.begin()+1;}
int query(int root,int l,int r,int L,int R){
     if(l>=L&&r<=R){
        return tree[root];
     }
     int ans=0;
     if(L<=mid)ans=max(ans,query(root<<1,l,mid,L,R));
     if(R>mid)ans=max(ans,query(root<<1|1,mid+1,r,L,R));
     return ans;
}
void add(int root,int l,int r,int x,int pos){
      if(l==r){
        tree[root]=x;
        return;
      }
      if(pos<=mid)add(root<<1,l,mid,x,pos);
      else add(root<<1|1,mid+1,r,x,pos);
      tree[root]=max(tree[root<<1],tree[root<<1|1]);
      return;
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].a>>a[i].b;
        a[i].i=i;
        v.push_back(a[i].b);
    }
    sort(a+1,a+1+n,[](node x,node y){return x.a>y.a;});
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());//去离散化
    for(int i=1;i<=n;i++){
        a[i].b=getid(a[i].b);
    }
    for(int i=1;i<=n;i++){
        res[a[i].i]=query(1,1,n,a[i].b,n)+1;//找bi到n这个区间中最大的重要程度是多少
        add(1,1,n,res[a[i].i],a[i].b);//更新树
    }
    for(int i=1;i<=n;i++){
        cout<<res[i]<<endl;
    }
    return 0;
}