题意：有两个长度分别为p+1和q+1的序列，每个序列中的各个元素互不相同，且都是1~n²之间的整数，两个序列的第一个元素都是1，问A和B的最长公共子序列的长度

分析：由于在同一个序列中元素互不相同，可以转化LCS问题为LIS问题，使用了“置换的思想”，有点类似于“离散化”，然后用stl的lower_bound函数实现log级别的查找，使得整个复杂度为nlogn

代码：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 using namespace std; 6 #define DEBUG 7 const int MAXN = 250 * 250; 8 const int INF = 0x3f3f3f3f; 9 int sun[MAXN];10 int s[MAXN];11 int g[MAXN];12 int main(){13 #ifndef DEBUG14     freopen("in.txt", "r", stdin);15 #endif16     int T, cas=1;17     scanf("%d", &T);18     while(T--){19         int N, p, q, x, i;20         memset(sun, 0, sizeof(sun));21         scanf("%d%d%d", &N, &p, &q);        //N is useless22         for(i=1; i<=p+1; i++) {23             scanf("%d", &x);24             sun[x]=i;25         }26         int n = 0;27         for(i=1; i<=q+1; i++){28             scanf("%d", &x);29             if(sun[x]) s[n++]=sun[x];30         }31         for(i=1; i<=n; i++) g[i]=INF;32         int ans=0;33         for(i=0; i
         
        
       
      

发现如果把数组名字设定为index则会报CE的错误，说是index是一个函数，⊙﹏⊙b汗