CDQ分治

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
int n;
int tr[100005];
int lowbit(int x) {
    return x & -x;
}
void add(int x, int k) {
    while (x <= n) {
        tr[x] = max(tr[x], k);
        x += lowbit(x);
    }
}
void assgin(int x, int k) {
    while (x <= n) {
        tr[x] = k;
        x += lowbit(x);
    }
}
int query(int x) {
    int res = 0;
    while (x) {
        res = max(res, tr[x]);
        x -= lowbit(x);
    }
    return res;
}
int a[100005], b[100005], p[100005], dp[100005];
array<int, 2> c[100005];
void cdq(int L, int R) {
    if (L == R) return;
    int mid = L + R >> 1;
    cdq(L, mid);
    for (int i = L ; i <= R ; i++) {
        p[i] = i;
    }
    sort(p + L, p + mid + 1, [&](const auto &x, const auto &y) {
        return c[x][0] < c[y][0];
    });
    sort(p + mid + 1, p + R + 1, [&](const auto &x, const auto &y) {
        return c[x][0] < c[y][0];
    });
    int j = L;
    for (int i = mid + 1 ; i <= R ; i++) {
        while (j <= mid && c[p[j]][0] <= c[p[i]][0]) {
            add(c[p[j]][1], dp[p[j]]);
            j++;
        }
        dp[p[i]] = max(dp[p[i]], query(c[p[i]][1]) + 1);
    }
    for (int i = L ; i <= mid ; i++) {
        assgin(c[p[i]][1], 0);
    }
    cdq(mid + 1, R);
}
void solve() {
    cin >> n;
    for (int i = 1 ; i <= n ; i++) {
        cin >> a[i];
        c[a[i]][0] = i;
    }
    for (int i = 1 ; i <= n ; i++) {
        cin >> b[i];
        c[b[i]][1] = i;
    }
    for (int i = 1 ; i <= n ; i++) {
        dp[i] = 1;
    }
    cdq(1, n);
    int ans = 0;
    for (int i = 1 ; i <= n ; i++) {
        ans = max(ans, dp[i]);
    }
    cout << ans << "\n";
}
int main() {
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}