C++ 解法, 执行用时: 1711ms, 内存消耗: 493432K, 提交时间: 2021-12-26 15:22:04

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
typedef long long LL;
const int N=500005;
const int MOD=1e9+7;
const int MAX=1e9;
int add (int x,int y)   {x=x+y;return x>=MOD?x-MOD:x;}
int mul (int x,int y)   {return (LL)x*y%MOD;}
int dec (int x,int y)   {x=x-y;return x<0?x+MOD:x;}
int Pow (int x,int y)
{
	int now=1;
	while (y){if (y&1) now=mul(now,x);x=mul(x,x);y>>=1;}
	return now;
}
int n,e;
int a[N];
int rt[N],num;
int c[2][N*100],s1[N*100],s2[N*100];
int f[N];
int q[N],ed;
void modify (int &now,int l,int r,int x,int c0,int c1)
{
	num++;s1[num]=s1[now];s2[num]=s2[now];	
	c[0][num]=c[0][now];c[1][num]=c[1][now];
	now=num;
	c[0][now]=add(c[0][now],c0);
	c[1][now]=add(c[1][now],c1);
	if (l==r) return ;
	int mid=(l+r)>>1;
	if (x<=mid) modify(s1[now],l,mid,x,c0,c1);
	else 		modify(s2[now],mid+1,r,x,c0,c1);
}
int query (int now,int l,int r,int L,int R,int op)
{
	if (now==0) return 0;
	if (l==L&&r==R) return c[op][now];
	int mid=(l+r)>>1;
	if (R<=mid) 	return query(s1[now],l,mid,L,R,op);
	else if (L>mid) return query(s2[now],mid+1,r,L,R,op);
	else return add(query(s1[now],l,mid,L,mid,op),query(s2[now],mid+1,r,mid+1,R,op));
}
int L[N];

int main()
{
	scanf("%d%d",&n,&e);
	for (int u=1;u<=n;u++) scanf("%d",&a[u]);
	/*for (int u=1;u<=n;u++)
	{
		L[u]=u-1;
		while (L[u]>0&&a[u]<=a[L[u]]) L[u]=L[L[u]];
	}*/
	ed=0;
	for (int u=1;u<=n;u++)
	{
		while (ed>0&&a[u]<=a[q[ed]]) ed--;
		L[u]=q[ed];q[++ed]=u;
	}
	ed=0;
	for (int u=1;u<=n;u++)
	{
		f[u]=0;
		if (L[u]==0) f[u]=1;
		/*for (int i=u;i>L[u];i--)	
		{*/
			
			int i=u,c0,c1,sum;
			c0=dec(c[0][rt[i-1]],query(rt[i-1],1,MAX,max(a[u]-e+1,1),min(MAX,a[u]+e-1),0));
			c1=dec(c[1][rt[i-1]],query(rt[i-1],1,MAX,max(a[u]-e+1,1),min(MAX,a[u]+e-1),1));
			sum=0;
			sum=add(sum,mul(i,c0));
			sum=dec(sum,c1);
			f[u]=add(f[u],sum);
			
			i=L[u];
			
			c0=dec(c[0][rt[i-1]],query(rt[i-1],1,MAX,max(a[u]-e+1,1),min(MAX,a[u]+e-1),0));
			c1=dec(c[1][rt[i-1]],query(rt[i-1],1,MAX,max(a[u]-e+1,1),min(MAX,a[u]+e-1),1));
			sum=0;
			sum=add(sum,mul(i,c0));
			sum=dec(sum,c1);
			f[u]=dec(f[u],sum);
			
			/*f[u]=add(f[u],mul(u,c0));
			f[u]=dec(f[u],c1);*/
			
			
		//	f[u]=f[u]+c[rt[i-1]]-query(rt[i-1],1,MAX,max(a[u]-e+1,1),min(MAX,a[u]+e-1),1);
		//}
		
		rt[u]=rt[u-1];
		while (ed>0&&a[q[ed]]>=a[u])	
		{
			modify(rt[u],1,MAX,a[q[ed]],MOD-f[q[ed]],mul(MOD-f[q[ed]],u));
			ed--;
		}
		q[++ed]=u;
		modify(rt[u],1,MAX,a[u],f[u],mul(u,f[u]));
		
	//	printf("%d:%d %d\n",u,f[u],L[u]);
	}
	int ans=0;
	int mn=MAX+1;
	for (int u=n;u>=1;u--)
	{
		if (mn>a[u])  ans=add(ans,f[u]);
		mn=min(mn,a[u]);
	}
	printf("%d\n",ans);
	return 0;
}