雪人（snowman）

【from new_dtoj 3991: 雪人（snowman）】 题目描述 WZY堆了N个雪人，每个雪人都有一个可爱度Xi，WZY认为两串雪人a1,a2…an与b1,b2…bm和谐当且仅当

n=ma1-b1=a2-b2=…=an-bn

WZY现在要从一堆雪人中选择两串雪人A=[l1,r1],B=[l2,r2]（两串可以重叠，即若l1≤l2，l2可以小于等于r1），使得A和B和谐，现在WZY想知道对于所有的方案中，min（|l1-l2|,len(A)）的最大值。 len（A）为A中所含雪人的个数。因为WZY还要准备AK JSOI 2019，所以他把这个问题交给了你。 n<=5e5 题解 考试只会$n^2$暴力50分，这里要orz slz szm 考虑到题目变形成a1-a2=b1-b2,a2-a3=b2-b3……所以我们可以先差分，然后把结果做一个hash 接着考虑二分长度，求出所有这些长度的hash值，并且记录下每个长度的左端点，如果说我们找到两个串hash值相同，并且左端点距离不小于二分的长度，说明这个长度还能再长，否则要缩短。这题还可以用SA实现 效率$O(nlo{g}^{2}n)-O(nlogn)$（一个排序，一个hash表）

#include <cstdio> #include <algorithm> #include <string> #define N 500005 #define U unsigned long long #define K 793999 #define E register #define _(d) while(d(isdigit(c=getchar()))) inline int R(){ int x;char c;_(!);x=(c^48); _()x=(x<<3)+(x<<1)+(c^48);return x; } int n,a[N],ans,l,r,d,s,q[N];U h[N],f[N],b[N]; bool C(E int x,E int y){return f[x]<f[y]||f[x]==f[y]&&x<y;} int main(){ n=R();b[0]=1; for (E int i=1;i^n+1;i++) a[i]=R(),b[i]=b[i-1]*K, h[i]=h[i-1]*K+(U)(a[i]-a[i-1]+1e9); l=0;r=n/2+1; while(l<r){ d=l+r+1>>1;bool J=0; for (E int i=1,j=d-1;j^n+1;i++,j++) f[i]=h[j]-h[i-1]*b[j-i+1],q[i]=i; std::sort(q+1,q+n-d+3,C); for (E int i=1,j=1;i^n-d+3;i=j){ while(f[q[j]]==f[q[i]] && j<=n-d+2) j++; s=q[j-1]-q[i];if (s>=d){J=1;break;} } if (J) l=d;else r=d-1; } return printf("%d\n",l),0; }