[BZOJ]2119: 股市的预测

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
const int MAXN=3e5+10;
const double eps=1e-8;
#define ll long long
using namespace std;
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch==‘-‘)f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-‘0‘,ch=getchar();
    return x*f;
}

int a[MAXN];
vector<int>vec;
int base,n;

int txt[MAXN],sa[MAXN],td[MAXN],t1[MAXN],t2[MAXN],rank1[MAXN],rank2[MAXN],rank3[MAXN];

bool cmp(int f[],int t,int w,int k){return f[t]==f[w]&&f[t+k]==f[w+k];}

void Sa(){
    int *rank1=t1;int *td=t2;
    int m=base+5;
    for(int i=0;i<m;i++)txt[i]=0;
    for(int i=0;i<n;i++)txt[a[i]]++,rank1[i]=a[i];
    for(int i=1;i<m;i++)txt[i]+=txt[i-1];
    for(int i=n-1;i>=0;i--)sa[--txt[a[i]]]=i;
    for(int k=1;k<=n;k<<=1){
	int p=0;
	for(int i=n-k;i<n;i++)td[p++]=i;
	for(int i=0;i<n;i++)if(sa[i]>=k)td[p++]=sa[i]-k;
	for(int i=0;i<m;i++)txt[i]=0;
	for(int i=0;i<n;i++)txt[rank1[i]]++;
	for(int i=1;i<m;i++)txt[i]+=txt[i-1];
	for(int i=n-1;i>=0;i--)sa[--txt[rank1[td[i]]]]=td[i];
	swap(td,rank1);rank1[sa[0]]=0;
	p=1;
	for(int i=1;i<n;i++)rank1[sa[i]]=cmp(td,sa[i],sa[i-1],k)?p-1:p++;
	if(p>=n)return ;
	m=p;
    }
}

int h[MAXN],H[MAXN];

void HH(){
    for(int i=0;i<n;i++)rank2[sa[i]]=i;
    memset(H,0,sizeof(H));
    for(int i=0;i<n;i++){
	if(rank2[i]==0)continue;
	int t=sa[rank2[i]-1];int k=0;int w=i;
	if(i==0||H[i-1]<=1)k=0;
	else k=H[i-1]-1,t+=k,w+=k;
	while(t<n&&w<n){
	    if(a[t]==a[w])k++;
	    else break;
	    t++;w++;
	}
	H[i]=k;h[rank2[i]]=k;
    }
}


void HH1(){
    for(int i=0;i<n;i++)rank3[sa[i]]=i;
    memset(H,0,sizeof(H));
    for(int i=0;i<n;i++){
	if(rank3[i]==0)continue;
	int t=sa[rank3[i]-1];int k=0;int w=i;
	if(i==0||H[i-1]<=1)k=0;
	else k=H[i-1]-1,t+=k,w+=k;
	while(t<n&&w<n){
	    if(a[t]==a[w])k++;
	    else break;
	    t++;w++;
	}
	H[i]=k;h[rank3[i]]=k;
    }
}


int dp[MAXN][21],ma[MAXN],dp1[MAXN][21];

void ST(){
    inc(i,2,n)ma[i]=ma[i/2]+1;
    for(int i=1;i<n;i++)dp[i][0]=h[i];
    for(int j=1;j<=20;j++){
	for(int i=1;i+(1<<j)<=n;i++){
	    dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
	}
    }
}

void ST1(){
    for(int i=1;i<n;i++)dp1[i][0]=h[i];
    for(int j=1;j<=20;j++){
	for(int i=1;i+(1<<j)<=n;i++){
	    dp1[i][j]=min(dp1[i][j-1],dp1[i+(1<<(j-1))][j-1]);
	}
    }
}

int get_min(int l,int r){
    if(l>r)swap(l,r);
    l++;
    int k=r-l+1;k=ma[k];
    return min(dp[l][k],dp[r-(1<<k)+1][k]);
}

int get_Min(int l,int r){
    if(l>r)swap(l,r);
    l++;
    int k=r-l+1;k=ma[k];
    return min(dp1[l][k],dp1[r-(1<<k)+1][k]);
}

int main(){
    n=read();int m=read();
    for(int i=0;i<n;i++)a[i]=read();
    for(int i=1;i<n;i++)a[i-1]=a[i]-a[i-1],vec.pb(a[i-1]);
    sort(vec.begin(),vec.end());
    base=unique(vec.begin(),vec.end())-vec.begin();
    n--;
    for(int i=0;i<n;i++)a[i]=lower_bound(vec.begin(),vec.begin()+base,a[i])-vec.begin()+1;
    a[n]=0;n++;
    Sa();HH();ST();
    reverse(a,a+n-1);
    Sa();HH1();ST1();
    ll ans=0;
    for(int l=1;l<n;l++){
	for(int i=0;i+m+l<=n;i+=l){
	    int t1=i;int t2=i+m+l;
	    int min1=min(l,get_min(rank2[t1],rank2[t2]));
	    int min2=min(l,get_Min(rank3[n-2-t1],rank3[n-2-t2]));
	    ans+=max(0,min1+min2-l);
	}
    }
    printf("%lld\n",ans);
}