小石的妹子

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

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

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

样例输入:
5
1 4
2 2
3 3
4 1
5 5

样例输出:
2
3
2
2
1

题解：
先按照a从大到小排序，对于第i个女生，她的rk[i] = max({rk[j]}) + 1 (b[j] > b[i])
其中max({rk[j]})是在现有的b[j]比b[i]大的女生中rk最大的那个值。
所以线段树维护最大值，b[i]为下标，rk[i]为值，线段树初始化为0，每次单点更新。由于b的范围大，需要首先离散化。

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rap(i, a, n) for(int i=a; i<=n; i++)
#define rd(a) scanf("%d", &a)
#define al(x)  x + 1, x + 1 + n
#define inf 0x3f3f3f3f
const int maxn = 2e5 + 10;
const int maxm = 5e5 + 10;
const ll mod = 998244353;
const double pi = acos(-1.0);
const double eps = 1e-8;

struct node1{
  int l, r;
  int v;
}tr[maxn << 2];

int n;
int d[maxn];
int rk[maxn];
struct node2{
  int a, b, id;
}x[maxn];

bool cmp(node2 x, node2 y){
  return x.a > y.a;
}

void pushup(int u){
  tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v);
}

void build(int u, int l, int r){
  tr[u] = {l, r};
  if(l == r){
    tr[u] = {l, r, 0};
    return ;
  }
  int mid = l + r >> 1;
  build(u << 1, l, mid);
  build(u << 1 | 1, mid + 1, r);
  pushup(u);
}

void update(int u, int x, int v){
  if(tr[u].l == x && tr[u].r == x){
    tr[u].v = v;
    return  ;
  }
  int mid = tr[u].l + tr[u].r >> 1;
  if(x <= mid)  update(u << 1, x, v);
  else          update(u << 1 | 1, x, v);
  pushup(u);
}

int query(int u, int l, int r){
  if(l <= tr[u].l && tr[u].r <= r){
    return tr[u].v;
  }
  int mid = tr[u].l + tr[u].r >> 1;
  int ans = 0;
  if(l <= mid)  ans = query(u << 1, l, r);
  if(r > mid)   ans = max(ans, query(u << 1 | 1, l, r));
  return ans;
}

int main(){
  rd(n);
  rap(i, 1, n){
    rd(x[i].a), rd(x[i].b);
    x[i].id = i;
    d[i] = x[i].b;
  }
  sort(al(x), cmp);
  sort(al(d));
  int m = unique(al(d)) - (d + 1);
  rap(i, 1, n){
    x[i].b = lower_bound(d + 1, d + m + 1, x[i].b) - d;
  }
  build(1, 1, n);
  rap(i, 1, n){
    rk[x[i].id] = query(1, x[i].b, n) + 1;
    update(1, x[i].b, rk[x[i].id]);
  }
  rap(i, 1, n){
    printf("%d\n", rk[i]);
  }
  return 0;
}