记录编号	252052	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]股市的预测	最终得分	100
用户昵称	/k	是否通过	通过
代码语言	C++	运行时间	2.940 s
提交时间	2016-04-19 11:03:27	内存使用	76.62 MiB

#include <cstdio>
#include <iostream>
#include<cstring>
#include <map>

#define MB 500100

using namespace std;

map<int,int>ma;
int K,n,m,pr;
int w[MB],nw[MB];
struct u
{
	struct uu
	{
		int z;
		int y;
		int zz;
	}c[MB*4];
	int s[MB],rk[MB],xxx[MB],yyy[MB],nx[MB],sa[MB],h[MB];
	void ghzsz()
	{
		int *x=xxx,*y=yyy;
		for(int i=0;i<n;i++)
		    s[x[i]=w[i]]++;
		for(int i=1;i<=m;i++)
		    s[i]+=s[i-1];
		for(int i=n-1;i>=0;i--)
		    sa[--s[x[i]]]=i;
		for(int j=1,p=1;p<n;j<<=1,m=p)
		{
			p=-1;
			for(int i=n-j;i<n;i++)
				y[++p]=i;
			for(int i=0;i<n;i++)
			    if(sa[i]>=j)
			    	y[++p]=sa[i]-j;
			for(int i=0;i<n;i++)
			    nx[i]=x[y[i]];
			for(int i=0;i<=m;i++)
			    s[i]=0;
			for(int i=0;i<n;i++)
			{
			    s[nx[i]]++;
			}
			for(int i=1;i<=m;i++)
			    s[i]+=s[i-1];
			for(int i=n-1;i>=0;i--)
			    sa[--s[nx[i]]]=y[i];
			int *t=x;
			x=y;
			y=t;
			x[sa[0]]=0;
			p=1;
			for(int i=1;i<n;i++)
			{
				if(!(t[sa[i]]==t[sa[i-1]]&&t[sa[i]+j]==t[sa[i-1]+j]))
				    ++p;
				x[sa[i]]=p-1;
			}
  		}
	}

	void gjs(int z,int y,int d)
	{
		c[d].z=z;
		c[d].y=y;
		if(z==y)
		{
			c[d].zz=h[z];
			return;
		}
		int mid=(z+y)>>1;
		gjs(z,mid,d<<1);
		gjs(mid+1,y,d<<1|1);
		c[d].zz=min(c[d<<1].zz,c[d<<1|1].zz);
		return;
	}

	int gw(int z,int y,int d)
	{
		if(z==c[d].z&&y==c[d].y)
		    return c[d].zz;
		int mid=(c[d].z+c[d].y)>>1;
		if(y<=mid)
		    return gw(z,y,d<<1);
		if(z>mid)
		    return gw(z,y,d<<1|1);
		return min(gw(z,mid,d<<1),gw(mid+1,y,d<<1|1));
	}

	void geth()
	{
		int k=0,j=0;
		for(int i=0;i<n;h[rk[i++]]=k)
		{
			for(k?--k:0,j=sa[rk[i]-1];w[i+k]==w[j+k];k++);
		}
	}

	void gmain()
	{
		memset(s,0,sizeof(s));
		memset(rk,0,sizeof(rk));
		memset(sa,0,sizeof(sa));
		memset(h,0,sizeof(h));
		++n;
		ghzsz();
		--n;
		for(int i=1;i<=n;i++)
			rk[sa[i]]=i;
		geth();
		gjs(1,n,1);
	}

}A,B;

int main()
{
	freopen("nt2011_stock.in","r",stdin);
	freopen("nt2011_stock.out","w",stdout);
	scanf("%d%d",&n,&K);
	for(int i=0;i<n;i++)
	    scanf("%d",&w[i]);
	for(int i=0;i<n;i++)
	    w[i]=w[i+1]-w[i];
	for(int i=0;i<n;i++)
	{
		if(ma.count(w[i]))
		    w[i]=ma[w[i]];
		else
		{
			ma[w[i]]=++m;
			w[i]=m;
		}
	}
	++m;
	A.gmain();
	for(int i=0;i<n;i++)
	    nw[i]=w[n-i-1];
	for(int i=0;i<n;++i)
	    w[i]=nw[i];
	B.gmain();
	for(int j=1;j<=n;j++)
	    for(int i=0;i<n&&i+K+j+1<n;i+=j)
	    {
			int k=i+K+j;
			int len=min(A.gw(min(A.rk[i],A.rk[k])+1,max(A.rk[i],A.rk[k]),1),j)+min(j,B.gw(min(B.rk[n-i-1],B.rk[n-k-1])+1,max(B.rk[n-i-1],B.rk[n-k-1]),1))-1;
			if(len+1>j)
			    pr+=len-j+1;
	    }
	printf("%d",pr);
	getchar();
	getchar();
}