13711번: LCS 4

https://www.acmicpc.net/problem/13711


$O(N\lg N)$

Ai를 i로 바꿔 생각하면 LIS를 구하는 문제와 동치이다.

#include<cstdio>
#include<algorithm>
using namespace std;
const int MXN = 1e5;
int idx[MXN + 1], dp[MXN], n, x;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &x), idx[x] = i;
    for (int i = 0; i < n; i++) {
        scanf("%d", &x);
        dp[i] = n;
        *lower_bound(dp, dp + i, idx[x]) = idx[x];
    }
    printf("%d", lower_bound(dp, dp + n, n) - dp);
    return 0;
}