对于每个位置求出L[i]表示左边最大的j，满足从j开始到i-1中存在第一个子序列

R[i]表示右边最小的j，满足从j开始到i-1中存在第二个子序列

然后枚举颜色是相遇点的位置，如果L[i]左边、R[i]右边存在一样的颜色，则可行

 

#include
     
      #define N 1000010inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}int n,k,m,l,i,j,t,a[N],c[N],nxt[N],loc[N],f[N],L[N],R[N],cnt[N],ret,ans;bool vis[N],can[N];int main(){  read(n),read(k);  for(i=1;i<=n;i++)read(c[i]);  read(m),read(l);  for(i=1;i<=m;i++)read(a[i]);  for(i=m+l-1;i>=m;i--)read(a[i]);  for(i=1;i<=n;i++)loc[i]=n+1;  for(i=n;i;i--)nxt[i]=loc[c[i]],loc[c[i]]=i;  for(i=1;i<=n;i++){    L[i]=m>1?f[1]:i;    if(c[i]==a[m-1])for(f[m-1]=i,j=m-2;j;j--)while((t=f[j]?nxt[f[j]]:loc[a[j]])
      
       1?f[m+l-1]:i;    if(c[i]==a[m+1])for(f[m+1]=i,j=m+2;j
       
        <=n?nxt[f[j]]:loc[a[j]])>f[j-1])f[j]=t;  }  for(i=1;i<=n;i++)if(L[i]>1&&R[i]
        
         R[i];j--)cnt[c[j]]++;    for(j=1;j
         
          =n)break;    for(j=R[i];j>R[i-1];j--)if(!(--cnt[c[j]])&&vis[c[j]])ret--,vis[c[j]]=0;    for(j=L[i-1];j