求助,只有10分

P1439 【模板】最长公共子序列

lilong @ 2022-07-06 16:57:24

树状数组版,样例都过不了,求查错

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,a[100001],b[100001],c,d[1000001],ans;
int lowbit(int x)
{
    return x & -x;
}
void xg(int x,int y)
{
    for(int i=x;i<=n;i+=lowbit(i))
        d[i]=max(d[i],y);
}
int cx(int x)
{
    int ans=0;
    for(int i=x;i>0;i-=lowbit(i))
        ans=max(ans,d[i]);
    return ans;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
        cin>>c,b[c]=i;
    for(int i=1;i<=n;i++)
    {
        d[i]=cx(b[a[i]])+1;
        xg(b[a[i]],d[i]);
        ans=max(ans,d[i]);
    }   
    cout<<ans;
    return 0;
}

|