题目: 友好城市

• 数据量 $2e5$

思路

• 选择其中一岸的城市排序，再求出另一岸的最长上升子序列

输入

7
22 4
2 6
10 3
15 12
9 8
17 17
4 2

输出

4

代码 $O(nlogn)$

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 2e5+10;
int dp[N],n;
pair<int,int> w[N];

int main(){
    cin >> n;
    for(int i=0;i<n;++i) scanf("%d%d",&w[i].first,&w[i].second);

    sort(w,w+n);

    int len = 0;
    dp[0] = -0x3f3f3f3f;
    for(int i=0;i<n;++i){
        int l = 0,r = len;
        while(l < r){
            int mid = l + r + 1 >> 1;
            if(dp[mid] < w[i].second) l = mid;
            else r = mid - 1;
        }
        len = max(len,r + 1);
        dp[r + 1] = w[i].second;
    }
    cout << len << endl;
    return 0;
}