获得原数列的差分数列，离散化后接在一起，中间用没有出现过的数分隔，于是问题就转化成求这个数列的最长重复子串，且每一段上都至少有一个子串。

求出后缀数组，二分答案即可。

1 #include
     
       2 #define R register 3 using namespace std; 4 const int N=1010,M=1000010,oo=2e9; 5 int n,m,tot,s[M],a[M],numpos[M]; 6 int x[M<<1],y[M<<1],sa[M<<1],rank[M],h[M],height[M],cnt[M],bel[M]; 7 int cmp(const int xx,const int yy){
   return a[xx]
      
       n-k;i--) y[++num]=i;16         for(R int i=1;i<=n;i++) if(sa[i]>k) y[++num]=sa[i]-k;17         for(R int i=1;i<=n;i++) cnt[x[i]]++;18         for(R int i=2;i<=m;i++) cnt[i]+=cnt[i-1];19         for(R int i=n;i;i--) sa[cnt[x[y[i]]]--]=y[i];20         for(R int i=1;i<=m;i++) cnt[i]=0;21         swap(x,y);22         x[sa[1]]=num=1;23         for(R int i=2;i<=n;i++){24             if(y[sa[i]]!=y[sa[i-1]]||y[sa[i]+k]!=y[sa[i-1]+k]) num++;25             x[sa[i]]=num;26         }27         if(num>=n) break;28         m=num;29     }30     for(R int i=1;i<=n;i++) rank[sa[i]]=i;31     int t=0;32     for(R int i=1;i<=n;i++){33         if(t) t--;34         while(rank[i]-1&&s[i+t]==s[sa[rank[i]-1]+t]) t++;35         h[i]=t,height[rank[i]]=t;36     }37 }38 bool vis[N];39 bool check(int k){40     memset(vis,0,sizeof(vis));41     vis[0]=1;42     int minh=oo,cc=0;43     for(int i=1;i<=n;i++){44         minh=min(minh,height[i]);45         if(minh
       
        =1&&!vis[bel[sa[i-1]]]) vis[bel[sa[i-1]]]=1,cc++;52             if(cc>=tot) return 1;53         }54     }55     return 0;56 }57 int main(){58     int t1,t2,t3,div=1000000000;59     scanf("%d",&tot);60     for(R int i=1;i<=tot;i++){61         scanf("%d%d",&t1,&t2);62         for(int j=1;j
        
         >1;77         if(check(mid)) l=mid+1,ans=mid;78         else r=mid-1;79     }80     printf("%d",ans+1);81     return 0;82 }