T3. 雪人 【题目背景】 大佬WZY在AK NOIP 2018后，决定去冰天雪地的Y城堆雪人。 【问题描述】 WZY堆了N个雪人，每个雪人都有一个可爱度Xi，WZY认为两串雪人与和谐当且仅当 WZY现在要从一堆雪人中选择两串雪人（两串可以重叠，即若，可以小于等于），使得A和B和谐，现在WZY想知道对于所有的方案中， 的最大值。为A中所含雪人的个数。因为WZY还要准备AK JSOI 2019，所以他把这个问题交给了你。 【输入格式】 输入文件名为snowman.in。 输入文件第一行为一个正整数N，表示雪人的个数。 输入文件第二行为N个整数：X1，X2，…XN。 【输出格式】 输出文件名为snowman.out。 输出文件仅一行一个整数，为 的最大值。 【输入输出样例1】
snowman.in
10
1 2 3 4 5 6 7 8 9 10
snowman.out
5
【输入输出样例1说明】 应选A=[1,5],B=[6,10]，此时，min(|6-1|,5)=5;
【数据规模与约定】
Subtask 1 10%：?≤500。
Subtask 2 20%：?≤5000。
Subtask 3 50%：N≤100000
Subtask 4 20%：?≤500000,0≤??≤100000000
题解 ：
考虑后缀数组。
其实和这道题洛谷P2743是可以一样的做法（虽然洛谷的弱很多）。
我们现将原数组差分，然后就变成了求两个子串的匹配。
我们先求出和数组，然后考虑二分答案。
对于每个二分出的每个答案，我们只需要考虑在 的串里
是否 .
注意由于题中给的值很大,并且由于
时间复杂度。
还有一位神犇写了 ，大家可以看一看
https://blog.csdn.net/liankewei123456/article/details/83381836
（ORZLKW）
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define repd(i,a,b) for(int i=a;i>=b;i--)
#define For(i,a,b) for(int i=a;i<b;i++)
#define Ford(i,a,b) for(int i=a;i>b;i--);
#define _(d) while(d(isdigit(ch=getchar())))
#define in inline
typedef long long ll;
template<class T>T read(){T x,f=1;char ch;_(!) ch=='-'?f=-1:f;x=ch-48;_() x=x*10+ch-48;return f*x;}
using namespace std;
const int N=8e6+4;
int l,s[N],str[N],m,orzlkw;
int sa[N],_rank[N],t2[N],c[N],h[N];
in void rsort(int n,int *x,int *y){
For(i,0,m) c[i]=0;
For(i,0,n) c[x[y[i]]]++;
For(i,1,m) c[i]+=c[i-1];
repd(i,n-1,0) sa[--c[x[y[i]]]]=y[i];
}
in bool cmp(int *f,int a,int b,int L){return f[a]==f[b]&&f[a+L]==f[b+L];}
in void getsa(int n){
int *x=_rank,*y=t2;
For(i,0,n) x[i]=s[i],y[i]=i;
m=orzlkw+100;rsort(n,x,y);int p=0;
for(int k=1;p<n;k<<=1,m=p){
p=0;
For(i,n-k,n) y[p++]=i;
For(i,0,n) if(sa[i]>=k) y[p++]=sa[i]-k;
rsort(n,x,y);swap(x,y);
p=1;x[sa[0]]=0;
For(i,1,n){
x[sa[i]]=cmp(y,sa[i-1],sa[i],k)?p-1:p++;
}
}
}
in void get_h(int n){
int k=0,j;
rep(i,0,n) _rank[sa[i]]=i;
For(i,0,n){
if(k) k--;j=sa[_rank[i]-1];
while(s[i+k]==s[j+k]&&(j+k<=n))k++;
h[_rank[i]]=k;
}
}
in bool check(int k,int n){
int mi=sa[1],mx=sa[1];
rep(i,2,n){
if(h[i]>=k&&i<=n){
mi=min(mi,sa[i]);
mx=max(mx,sa[i]);
if(mx-mi>k) return 1;
continue;
}
mi=mx=sa[i];
}
return 0;
}
int b[N];
in void input(){
For(i,0,l) str[i]=read<int>();
For(i,0,l-1) str[i]=str[i+1]-str[i],b[i]=str[i];
sort(b,b+l); orzlkw=unique(b,b+l)-b;
For(i,0,l-1) str[i]=lower_bound(b,b+orzlkw,str[i])-b;
For(i,0,l) s[i]=str[i]+48;s[--l]=0;
}
in void work(){
int li=1,ri=l/2,ans=0;
while(li<=ri){
int mid=(li+ri)>>1;
if(check(mid,l)) ans=mid,li=mid+1;
else ri=mid-1;
}
ans++;
printf("%d\n",ans);
}
int main(){
//freopen("a.in","r",stdin);
//freopen("a.out","w",stdout);
l=read<int>();
input();
getsa(l+1); get_h(l);
work();
return 0;
}
