P2463 [SDOI2008]Sandy的卡片[差分+串拼接后缀数组]

P2463 [SDOI2008]Sandy的卡片

套路都差不多，都是差分后二分答案找lcp。只是这题要把多个串拼接起来成为一个大串，中间用某些值域中没有的数字相隔（最好间隔符都不一样想想为什么），排序后在二分答案，开个栈统计即可（保证单次check复杂度O(N)）。

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int N=+;//m<=101不是m<=100大小没算好坑死我了

 template<typename T>inline char MAX(T&A,T B){return A<B?(A=B,):;}

 template<typename T>inline char MIN(T&A,T B){return A>B?(A=B,):;}

 inline int read(){

     int f=,x=;char c;while(!isdigit(c=getchar()))if(c=='-')f=;

     while(isdigit(c))x=(x<<)+(x<<)+(c^),c=getchar();return f?-x:x;

 }

 int a[N],pos[N],bin[N],vis[N],tot;

 int n,l,x,ans,tmp,mid,L,R=;

 int sa[N],h[N],cnt[N],y[N],rk[N],p,m;

 inline void suffix_sort(){m=;

     for(register int i=;i<=tot;++i)++cnt[rk[i]=a[i]];

     for(register int i=;i<=m;++i)cnt[i]+=cnt[i-];

     for(register int i=tot;i;--i)sa[cnt[rk[i]]--]=i;

     for(register int k=;k<tot;k<<=,p=){

         for(register int i=tot-k+;i<=tot;++i)y[++p]=i;

         for(register int i=;i<=tot;++i)if(sa[i]>k)y[++p]=sa[i]-k;

         for(register int i=;i<=m;++i)cnt[i]=;

         for(register int i=;i<=tot;++i)++cnt[rk[y[i]]];

         for(register int i=;i<=m;++i)cnt[i]+=cnt[i-];

         for(register int i=tot;i;--i)sa[cnt[rk[y[i]]]--]=y[i];

         swap(rk,y);rk[sa[]]=p=;

         for(register int i=;i<=tot;++i)rk[sa[i]]=y[sa[i]]==y[sa[i-]]&&y[sa[i]+k]==y[sa[i-]+k]?p:++p;

         if(p==tot)break;m=p;

     }p=;

     for(register int i=;i<=tot;h[rk[i]]=p,p?--p:,++i)while(a[i+p]==a[sa[rk[i]-]+p]&&++p);

 }

 inline int check(int k){

     for(register int i=;a[sa[i]]<=;++i){

         if(h[i]<k){while(x)vis[bin[x--]]=;}

         if(!vis[pos[sa[i]]])vis[pos[sa[i]]]=,bin[++x]=pos[sa[i]];

         if(x==n)return ;

     }

     return ;

 }

 int main(){//freopen("tmp.in","r",stdin);

     n=read();

     for(register int i=;i<=n;++i){

         l=read();a[++tot]=read();pos[tot]=i;

         for(register int j=;j<=l;++j)a[++tot]=read(),a[tot-]=a[tot]-a[tot-]+,pos[tot]=i;

         a[tot]=i+;

     }

     suffix_sort();

     while(L<=R){

         mid=L+R>>;

         if(check(mid))ans=mid,L=mid+;

         else R=mid-;

     }

     printf("%d\n",ans+);

     return ;

 }