思路:
一种分治的神做法.建议去看原论文[2011年集训队作业]
#include<map>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define INF 0x3f3f3f3f
#define N 50010
int n,lim;
int len[N];
inline void pre(int n){
for(int i=2;i<=n;++i)len[i]=len[i>>1]+1;
}
int Read[N],s[N],ss[N],v[N],nv[N],q[N],c[N];
inline bool cmp(int x,int y,int hl,int n){
return v[x]==v[y]&&((x+hl>n&&y+hl>n)||(x+hl<=n&&y+hl<=n&&v[x+hl]==v[y+hl]));
}
struct SuffixArray{
int rk[N],h[N],sa[N],rmqh[N][16];
inline void Init(int s[],int n,int m){
int i,j,k,hl,id;
for(i=1;i<=m;++i)c[i]=0;
for(i=1;i<=n;++i)++c[v[i]=s[i]];
for(i=2;i<=m;++i)c[i]+=c[i-1];
for(i=n;i>=1;--i)sa[c[v[i]]--]=i;
for(int d=1;;++d){
for(hl=1<<(d-1),id=0,i=n-hl+1;i<=n;++i)q[++id]=i;
for(i=1;i<=n;++i)if(sa[i]>hl)q[++id]=sa[i]-hl;
for(i=1;i<=m;++i)c[i]=0;
for(i=1;i<=n;++i)++c[v[q[i]]];
for(i=2;i<=m;++i)c[i]+=c[i-1];
for(i=n;i>=1;--i)sa[c[v[q[i]]]--]=q[i];
for(i=m=1;i<=n;++m,i=j+1){
for(j=i;j!=n&&cmp(sa[j],sa[j+1],hl,n);++j);
for(k=i;k<=j;++k)nv[sa[k]]=m;
}
if(--m==n)break;
for(i=1;i<=n;++i)v[i]=nv[i];
}
for(i=1;i<=n;++i)rk[sa[i]]=i;
for(i=1;i<=n;++i){
if(rk[i]==1)continue;
j=max(0,h[rk[i-1]]-1);
while(i+j<=n&&sa[rk[i]-1]+j<=n&&s[i+j]==s[sa[rk[i]-1]+j])++j;
h[rk[i]]=j;
}
for(i=1;i<=n;++i)rmqh[i][0]=h[i];
for(j=1;j<=15;++j)for(i=1;i+(1<<j)-1<=n;++i)rmqh[i][j]=min(rmqh[i][j-1],rmqh[i+(1<<(j-1))][j-1]);
}
inline int askrmq(int l,int r){
return min(rmqh[l][len[r-l+1]],rmqh[r-(1<<len[r-l+1])+1][len[r-l+1]]);
}
inline int getlcp(int x,int y){
int lins=min(rk[x],rk[y]),rins=max(rk[x],rk[y]);
if(lins==rins)return n-x+1;
else return askrmq(lins+1,rins);
}
}Steins,revSteins;
inline int lcp(int x,int y){
return Steins.getlcp(x,y);
}
inline int lcs(int x,int y){
return revSteins.getlcp(n-x+1,n-y+1);
}
inline bool same(int l1,int l2,int len){
return lcp(l1,l2)>=len;
}
map<int,int>M;int sav[N];
long long res;
inline void SteinsGate(int l,int r){
if(r-l+1<lim+2)return;
int mid=(l+r)>>1;
SteinsGate(l,mid),SteinsGate(mid+1,r);
int prelen,suflen,insl,insr,nowlen;
for(prelen=0;prelen<lim;++prelen){
suflen=lim-1-prelen;
insl=mid-prelen,insr=mid+suflen;
if(insl>=l&&insr<=r)
for(nowlen=1;insl-nowlen>=l&&insr+nowlen<=r;++nowlen)if(same(insl-nowlen,insr+1,nowlen))++res;
}
int lins,rins,anotherins,Lcp,Lcs,up,down;
for(anotherins=l;anotherins<=r;++anotherins){
if((anotherins>mid&&anotherins-mid-1>=lim)||(mid>anotherins&&mid-anotherins-1>=lim)){
lins=min(mid,anotherins),rins=max(mid,anotherins);
Lcp=lcp(lins,rins),Lcs=lcs(lins,rins);
down=-INF,up=INF;
down=max(down,rins-Lcs-lim+1);//rins-(x+m-1)<=lcs
up=min(up,lins+Lcp);//x-lins<=lcp
down=max(down,l-lim+rins-lins);//lins-(rins-(x+m-1))+1>=l
up=min(up,r+1+lins-rins);//rins+(x-lins)-1<=r
down=max(down,lins+1),up=min(up,rins-1);//lins<=x<=rins
down=max(down,lins+2-lim),up=min(up,rins-lim);//lins<=x+m-1<=rins
if(down<=up){
res+=up-down+1;
if(anotherins<mid&&down==anotherins+1)--res;
}
}
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("tt.in","r",stdin);
#endif
scanf("%d%d",&n,&lim);register int i;
for(i=0;i<n;++i)scanf("%d",&Read[i]);
for(--n,i=1;i<=n;++i)s[i]=Read[i]-Read[i-1];
for(i=1;i<=n;++i)sav[i]=s[i];sort(sav+1,sav+n+1);
int id=0;for(sav[0]=-INF,i=1;i<=n;++i)if(sav[i]!=sav[i-1])M[sav[i]]=++id;
for(i=1;i<=n;++i)s[i]=M[s[i]];
for(i=n;i>=1;--i)ss[i]=s[n+1-i];
pre(n),Steins.Init(s,n,id),revSteins.Init(ss,n,id);
SteinsGate(1,n);
cout<<res<<endl;
return 0;
}