记录编号	392586	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]股市的预测	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.814 s
提交时间	2017-04-08 10:41:59	内存使用	126.19 MiB

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=2e5+10;
int n,m,a[N],s[N];
int rank(int x){
	int l=1,r=n;
	while (l<r){
		int mid=(l+r)>>1;
		if (a[mid]>=x) r=mid;else l=mid+1;
	}
	return l;
}
int Wa[N],Wb[N],Ws[N],sa[N],r[N],h[N];
bool cmp(int *r,int x,int y,int l){
	return r[x]==r[y]&&r[x+l]==r[y+l];
}
void getsa(){
	int m=n,*x=Wa,*y=Wb,i,j,k;
	for (i=1;i<=n;i++) Ws[x[i]=s[i]]++;
	for (i=1;i<=m;i++) Ws[i]+=Ws[i-1];
	for (i=n;i;i--) sa[Ws[x[i]]--]=i;
	for (int l=1,p=0;p<n;m=p,l<<=1){
		for (i=n-l+1,p=0;i<=n;i++) y[++p]=i;
		for (i=1;i<=n;i++)
			if (sa[i]>l) y[++p]=sa[i]-l;
		for (i=0;i<=m;i++) Ws[i]=0;
		for (i=1;i<=n;i++) Ws[x[y[i]]]++;
		for (i=1;i<=m;i++) Ws[i]+=Ws[i-1];
		for (i=n;i;i--) sa[Ws[x[y[i]]]--]=y[i];
		swap(x,y);
		for (x[sa[1]]=p=1,i=2;i<=n;i++)
			x[sa[i]]=cmp(y,sa[i],sa[i-1],l)?p:++p;
	}
	for (i=1;i<=n;i++) r[sa[i]]=i;
	for (k=h[r[0]]=0,i=1;i<=n;h[r[i++]]=k)
	for (k?k--:0,j=sa[r[i]-1];s[i+k]==s[j+k];k++);
}
//求串s有多少个子串T,满足T存在长为(|T|-m)/2的border 
const int M=1e7;
struct Node{int l,r,v;}node[M];
int id,root[N],fa[N],size[N];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
int add(int x,int l,int r,int p){
	int now=++id;
	node[now]=node[x];
	node[now].v++;
	if (l!=r){
		int mid=(l+r)>>1;
		if (p>mid) node[now].r=add(node[x].r,mid+1,r,p);
			else node[now].l=add(node[x].l,l,mid,p);
	}
	return now;
}
int merge(int x,int y,int l,int r){
	if (!x||!y) return x|y;
	int now=++id,mid=(l+r)>>1;
	node[now].v=node[x].v+node[y].v;
	node[now].l=merge(node[x].l,node[y].l,l,mid);
	node[now].r=merge(node[x].r,node[y].r,mid+1,r);
	return now;
}
int query(int x,int l,int r,int L,int R){
	if (l>=L&&r<=R) return node[x].v;
	int mid=(l+r)>>1,ans=0;
	if (L<=mid) ans+=query(node[x].l,l,mid,L,R);
	if (R>mid) ans+=query(node[x].r,mid+1,r,L,R);
	return ans;
}
long long ans;
int q[N];
vector<int> S[N];
bool comp(int x,int y){return h[x]>h[y];}
void merge(int x){
	int lcp=h[x];
	if (!lcp) return;
	int a=find(x-1),b=find(x);
	if (size[a]>size[b]) swap(a,b);
	for (int i=S[a].size()-1;i>=0;i--){
		int v=S[a][i];
		ans+=query(root[b],1,n,v-m-lcp,v+m+lcp);
		ans-=query(root[b],1,n,v-m,v+m);
		S[b].push_back(v);
	}
	fa[a]=b;
	size[b]+=size[a];
	root[b]=merge(root[a],root[b],1,n);
}
int main()
{
	freopen("nt2011_stock.in","r",stdin);
	freopen("nt2011_stock.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	n--;
	for (int i=1;i<=n;i++) s[i]=a[i+1]-a[i];
	for (int i=1;i<=n;i++) a[i]=s[i];
	sort(a+1,a+n+1);
	for (int i=1;i<=n;i++) s[i]=rank(s[i]);
	getsa();
	for (int i=1;i<=n;i++){
		fa[i]=q[i]=i;
		size[i]=1;
		S[i].push_back(sa[i]);
		root[i]=add(0,1,n,sa[i]);
	}
	sort(q+1,q+n+1,comp);
	for (int i=1;i<=n;i++) merge(q[i]);
	printf("%lld\n",ans);
	return 0;
}