题解：AT_arc126_b [ARC126B] Cross-free Matching

fush · 2024-11-29 13:19:41 · 题解

题意

有两行，一行 n 个点，和 m 条线（从第一行的节点连向第二行的节点）。 现在问你最多留下多少线，能使任意两条线均不相交。

思路

为了方便描述，第 a 条线的第一行节点是 a_x，第二行节点是 a_y。

显然，两条相交的线 a, b 必然满足，a_x < b_x \land a_y > b_y 或是 a_x = a_x \lor a_y = b_y。

那么我们对 a_x 做升序，相等时 a_y 做降序（规避第二种情况）。

这样我们只需要对 a_y 求最长上升子序列即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
constexpr int N = 1e6 + 10;
struct A{int x, y;}a[N];
int f[N], tot, n, m;
int find(int x){
    int l = 0, r = tot;
    while(l < r){
        int mid = (l + r) >> 1;
        if(f[mid] < x)l = mid + 1;
        else r = mid;
    }
    return l;
}
int32_t main(){
    cin.tie(0)->sync_with_stdio(0);
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
        cin >> a[i].x >> a[i].y;
    sort(a + 1, a + 1 + m, [](A&i, A&j){return (i.x ^ j.x) ? (i.x < j.x) : (i.y > j.y);});
    f[tot = 1] = a[1].y;
    for(int i = 1; i <= m; i++){
        if(a[i].y > f[tot])f[++tot] = a[i].y;
        else f[find(a[i].y)] = a[i].y;
    }
    cout << tot << endl;
    return 0;
}