0pts玄关

Star_Sky_ @ 2024-09-20 13:23:16

#include <iostream>
#include <cstdio>

using namespace std;

int n, l, r, mid, cnt, ans;
int p1[100005], p2[100005], mp[100005], dp[100005]={1145140};

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++)scanf("%d", &p1[i]), mp[p1[i]]=i;
    for(int i=1; i<=n; i++)scanf("%d", &p2[i]), p2[i]=mp[p2[i]];

    for(int i=1; i<=n; i++){
        l=0, r=ans;
        while(l<=r){
            mid=(l+r)/2;

            if(dp[mid]>=p2[i]){
                cnt=mid;
                l=mid+1;
            }
            else r=mid-1;
        }

        ans=max(ans,cnt+1);
        dp[cnt+1]=p2[i];
    }

    printf("%d", ans);
    return 0;
}

by hefu1234 @ 2024-09-21 20:20:27

//
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int n,a[N],b[N],c[N],d[N],y;
map <int,int> mm;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i],mm[a[i]] = i;
    for(int i = 1; i <= n; i++) cin >> b[i],c[i] = mm[b[i]];

    for(int i = 1; i <= n; i++){
        if(c[i] > d[y]) d[++y] = c[i];
        else{
            int l = 0,r = y;
            while(l + 1 < r){
                int mid = (l + r) >> 1;
                if(d[mid] < c[i]) l = mid;
                else r = mid;
            }
            d[r] = c[i];
        }
    }
    cout << y <<'\n';
    return 0;
}