这个题目我AC之后看了一下别人的题解，基本上都是线段树，不过二分也可以。
这个题目很自然就肯定要对其中一个进行排序，排完序之后再处理另外一边，另一边记得离散化。
怎么处理呢，你仔细想想，找找规律就可以发现，其实我们就是在找递增子序列。
第一次找到的就是重要程度为1 的妹子，然后删除这些元素，继续第二次找，第二次找到的就是重要程度为二的妹子。
所以到每一个点，我们就只要根据它的大小来判断它应该放的位置（尽量靠前，并且小于这个数），然后更新这个位置，再返回这个位置，它所在的位置就是它的重要程度。
emmm 其实就是用一个数组，数组的每一个位置 i 存的就是到目前位置重要程度为 i 的最大值。
具体看代码吧。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
#include <string>
#include <iostream>
#include <map>
#define inf 0x3f3f3f3f
#define inf64 0x3f3f3f3f3f3f3f3f
using namespace std;
const int maxn = 2e5 + ;
typedef long long ll;
int num[maxn];
map<ll, ll>mp;
struct node
{
int l, r;
int sum;
}tree[*maxn];
struct edge
{
ll a, b, id, num, ans;
}ex[maxn]; bool cmp(edge a,edge b)
{
return a.a > b.a;
} bool cmp1(edge a,edge b)
{
return a.b < b.b;
} bool cmp2(edge a,edge b)
{
return a.id < b.id;
} int tot = ;
int ok(ll x)
{
if (x > num[]) return ;
if (x < num[tot])
{
tot++;
return tot;
}
int l = , r = tot, ans = ;
int mid = (l + r) >> ;
while (l <= r) {
int mid = (l + r) / ;
if (num[mid]<x) ans = mid, r = mid - ;
else l = mid + ;
}
return ans;
} int main()
{
int n;
scanf("%d", &n);
for (int i = ; i <= n; i++) {
scanf("%lld%lld", &ex[i].a, &ex[i].b), ex[i].id = i;
}
sort(ex + , ex + + n, cmp1);
for (int i = ; i <= n; i++) mp[ex[i].b] = i;
sort(ex + , ex + + n, cmp);
num[] = mp[ex[].b];
ex[].ans = ;
tot = ;
for(int i=;i<=n;i++)
{
int f = ok(mp[ex[i].b]);
// printf("%lld ex[%d]=%lld f=%d\n",mp[ex[i].b], i, ex[i].b, f);
num[f] = mp[ex[i].b];
ex[i].ans = f;
}
sort(ex + , ex + + n, cmp2);
for (int i = ; i <= n; i++) printf("%lld\n", ex[i].ans);
return ;
}
二分
网上的线段树的方法我感觉和逆序对有点像，就是首先还是把 b 离散化，然后对 a 进行排序，
然后从 1 ~ n 遍历，如果对于每一个 b 首先判断 b ~ n 有没有值，其实就是有没有比 b 大的再前面放过了，有的话就去最大值，重要程度就是 最大值+1 （这个是因为存进去的就是最大值）
没有那么重要程度就是 1 ，然后再更新这个点 b 把 b 的重要程度放到线段树的 b 这个位置以便后面的查询。
这个很好写的。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
#include <string>
#include <iostream>
#include <map>
#define inf 0x3f3f3f3f
#define inf64 0x3f3f3f3f3f3f3f3f
using namespace std;
const int maxn = 2e5 + ;
typedef long long ll;
map<ll, ll>mp;
struct node
{
int l, r;
int num;
}tree[*maxn];
struct edge
{
ll a, b, id, num, ans;
}ex[maxn]; bool cmp(edge a,edge b)
{
return a.a > b.a;
} bool cmp1(edge a,edge b)
{
return a.b < b.b;
} bool cmp2(edge a,edge b)
{
return a.id < b.id;
} void build(int id, int l, int r) {
tree[id].l = l;
tree[id].r = r;
if (l == r) {
tree[id].num = ;
return;
}
int mid = (l + r) >> ;
build(id << , l, mid);
build(id << | , mid + , r);
} int query(int id, int x, int y) {
int l = tree[id].l;
int r = tree[id].r;
if (x <= l && y >= r) {
// printf("id=%d sum=%d \n", id,tree[id].sum);
return tree[id].num;
}
int ans = ;
int mid = (l + r) >> ;
if (x <= mid) ans = max(ans, query(id << , x, y));
if (y > mid) ans = max(ans, query(id << | , x, y));
// printf("id=%d ans=%d l=%d r=%d x=%d y=%d \n", id, ans, l, r,x,y);
return ans;
} void push_up(int id) {
tree[id].num = max(tree[id << ].num , tree[id << | ].num);
} void update(int id, int x,int val) {
int l = tree[id].l;
int r = tree[id].r;
if (l == r) {
tree[id].num = val;
return;
}
int mid = (l + r) >> ;
if (x <= mid) update(id << , x,val);
else update(id << | , x,val);
push_up(id);
} int main()
{
int n;
scanf("%d", &n);
for (int i = ; i <= n; i++) {
scanf("%lld%lld", &ex[i].a, &ex[i].b), ex[i].id = i;
}
sort(ex + , ex + + n, cmp1);
for (int i = ; i <= n; i++) mp[ex[i].b] = i;
sort(ex + , ex + + n, cmp);
build(, , n);
for(int i=;i<=n;i++)
{
int f = query(, mp[ex[i].b], n) + ;
ex[i].ans = f;
update(, mp[ex[i].b],f);
}
sort(ex + , ex + + n, cmp2);
for (int i = ; i <= n; i++) printf("%lld\n", ex[i].ans);
return ;
}
逆序对 线段树