[POI 21 Stage 2] Criminals

作法：

第一個人從左到右跳的過程很明顯是用貪心最好，而如果考慮把這個過程反過來，就變成當我們決定好終點時，就一直往左邊跳，並且也是貪心的跳最近的，右邊也同理。而因為他給的條件保證一個人在跳的時候經過的顏色都不一樣，所以當我們考慮從左跳到右的人時，只要紀錄每個點往左跳（現在已經把整個過程反過來了）會跳到哪裡就可以了。而處理完這件事之後。就可以利用類似並查集的作法得到對於一個終點顏色，他往左跳到底會跳到誰。而從右邊出發的人也同理，可以找出對每個終點顏色，他往右跳到底會跳到誰。

這樣左邊和右邊就會分別跳到兩個點，叫他們 x 和 y 好了，這時候我們需要查詢 1 ~ x-1 之間和 y+1 ~ n 之間是否有一樣的數，這樣才可以讓他們兩人的起點顏色一樣。而這件事可以反過來想，只要處理出對於一個 u ，滿足 1 ~ u 和 v ~ n 之中有相同顏色的最大的 v 是誰就可以了，這只會花O( n ) 的時間。最後我傳上去後拿到 OK 99 分，加了輸入優化之後才拿100。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000000+10 ;
 
int getint()
{
     char c=getchar() ;
     while(c<'0' || c>'9') c=getchar() ;
     int x=0 ;
     while(1)
     {
          x=x*10+(c-'0') ;
          c=getchar() ;
          if(c<'0' || c>'9') return x ;
     }
}
 
vector<int> v[maxn] ;
 
int a[maxn] ;
int p[maxn],q[maxn] ;
int le[maxn],ri[maxn] ;
 
int num1[maxn],num2[maxn],R[maxn] ;
vector<int> ans ;
 
main()
{
     int n=getint(),k=getint() ;
     for(int i=1;i<=n;i++)
     {
          a[i]=getint() ;
          v[a[i]].push_back(i) ;
          ri[i]=n+1 ;
     }
     ri[n+1]=n+1 ;
 
     int m=getint(),l=getint() ;
     for(int i=1;i<=m;i++) p[i]=getint() ;
     for(int i=1;i<=l;i++) q[i]=getint() ;
     for(int i=1;i<m;i++) for(int j=0;j<v[p[i+1]].size();j++)
     {
          int x=v[p[i+1]][j] ;
          int id=lower_bound(v[p[i]].begin(),v[p[i]].end(),x)
                    -v[p[i]].begin()-1 ;
          if(id>=0) le[x]=v[p[i]][id] ;
          if(i!=1) le[x]=le[le[x]] ;
     }
 
     for(int i=1;i<l;i++) for(int j=0;j<v[q[i+1]].size();j++)
     {
          int x=v[q[i+1]][j] ;
          int id=lower_bound(v[q[i]].begin(),v[q[i]].end(),x)
                    -v[q[i]].begin() ;
          if(id<v[q[i]].size()) ri[x]=v[q[i]][id] ;
          if(i!=1) ri[x]=ri[ri[x]] ;
     }
 
     for(int i=1;i<=n;i++) num2[a[i]]++ ;
     for(int i=1 , j=1 , now=0;i<=n;i++)
     {
          num1[a[i]]++ ;
          if(num1[a[i]]==1 && num2[a[i]]) now++ ;
          while(j<=n)
          {
               num2[a[j]]-- ;
               if(!num2[a[j]] && num1[a[j]]) now-- ;
               if(!now) { num2[a[j]]++ ; now++ ; break ; }
               j++ ;
          }
          R[i]=j ;
     }
     for(int i=1;i<=n;i++) if(a[i]==p[m])
     {
          int x= (m==1 ? i : le[i]) ;
          int y= (l==1 ? i : ri[i]) ;
          if(x>1 && y<n && R[x-1]>=y+1)
               ans.push_back(i) ;
     }
     printf("%d\n",ans.size()) ;
     for(int i=0;i<ans.size();i++)
        printf("%d%c",ans[i],i+1==ans.size()?'\n':' ') ;
     if(ans.empty()) printf("\n") ;
}