枚举左端点$i$，那么可行的右端点$j$的最小值单调不下降，可以通过双指针求出，检验可以通过在后缀数组里检查相邻height值做到$O(1)$。

那么左端点为$i$，右端点在$[j,n]$，它对前面一段的贡献为定值，对后面一段的贡献为等差数列，线段树维护即可。

时间复杂度$O(n\log n)$。

 

#include
     
      #include
      
       const int N=100010,M=262150;int n,i,j,rk[N],sa[N],height[N],tmp[N],cnt[N],ta[M],tb[M];char s[N];void suffixarray(int n,int m){  int i,j,k;n++;  for(i=0;i
       
        =n-1)break;  }  for(j=rk[height[i=k=0]=0];i
        
         =y-x+1||height[k+1]>=y-x+1;}inline void up(int&a,int b){if(a>b)a=b;}void build(int x,int a,int b){  ta[x]=tb[x]=N;  if(a==b)return;  int mid=(a+b)>>1;  build(x<<1,a,mid),build(x<<1|1,mid+1,b);}void tag(int*v,int x,int a,int b,int c,int d,int p){  if(c<=a&&b<=d){up(v[x],p);return;}  int mid=(a+b)>>1;  if(c<=mid)tag(v,x<<1,a,mid,c,d,p);  if(d>mid)tag(v,x<<1|1,mid+1,b,c,d,p);}void dfs(int x,int a,int b){  if(a==b){    up(ta[x],tb[x]+a);    printf("%d\n",ta[x]+1);    return;  }  int mid=(a+b)>>1;  up(ta[x<<1],ta[x]),up(ta[x<<1|1],ta[x]);  up(tb[x<<1],tb[x]),up(tb[x<<1|1],tb[x]);  dfs(x<<1,a,mid),dfs(x<<1|1,mid+1,b);}int main(){  gets(s);n=strlen(s);  suffixarray(n,128);  build(1,0,n-1);  for(i=0;i
         
          =n)break;    tag(ta,1,0,n-1,i,j,j-i);    tag(tb,1,0,n-1,j,n-1,-i);  }  dfs(1,0,n-1);  return 0;}