Longest Increasing Subsequence for the problem on SPOJ (http://www.spoj.com/problems/XMEN/)

LCS.cpp

// http://www.spoj.com/problems/XMEN/
#include <algorithm>
#include <cstdio>
#include <stack>
#include <iostream>

using namespace std;

#define MAX_N 100005

//LONGEST COMMON SUBSEQUENCE O(nlogn)

int A[MAX_N];
int B[MAX_N];
int loc[MAX_N];

int n;

void allocate(){
    
    for (int i=1;i<=n;++i){
        loc[B[i]]=i;
    }    
}


int LIS(){ //using binary search
    
    int i,k,l,r,mid;
    A[1]=B[1]; k=1;
    
    for (int i=2;i<=n;++i){
        
        if (A[k]<B[i]) A[++k]=B[i];
        
        else{
            
            l=1; r=k;
            
            while (l<=r){
                mid=(l+r)/2;
                
                if (A[mid]<B[i])
                l=mid+1;
                else
                r=mid-1;
            }
            
            A[l]=B[i];
            
        }
        
    }
    
    return k;
}


int main(){
    
    int t;
    scanf("%d",&t);
    while (t--){
        scanf("%d",&n);
        
        for (int i=1;i<=n;++i)
            scanf("%d",&A[i]);
        for (int i=1;i<=n;++i)
            scanf("%d",&B[i]);
            
        allocate();
        
        for (int i=1;i<=n;++i){
            B[i]=loc[A[i]];
        }
        
            printf("%d\n",LIS());
    //reconstruct_print(lis_end,A,P);
    }
    

    
    

    return 0;
}