题目大意

　　有一个人要去直线上\(lm\)远处的地方，他会依次给他的机器发出\(n\)个指令。第\(i\)个指令为\(d_i\)。他的机器收到一个指令\(x\)后，如果向目的地方向前进\(xm\)后比当前离目的地更近，就会向前移动\(xm\)，否则什么都不会做。

　　现在，给你\(q\)个询问，第\(i\)个询问为\(a_i\)，问你能不能改变\(d_{a_i}\)，使得这个人不能到达目的地。你可以决定把\(d_{a_i}\)改成什么数。

　　\(n,q\leq 500000,1\leq d_i\leq {10}^9\)

题解

　　首先我们先算出执行前面\(i\)个指令后离终点的距离\(c_i\)

　　暴力的做法是用DP算出\(g_{i,j}\)：执行后面\(i\)~\(n\)的指令，离终点的距离为\(j\)，执行完后能不能到达终点。

　　然后就会发现一旦出现一个\(0\)，后面的\(1\)就会无意义。（因为可以修改成直接走到\(0\)这里）

　　那么我们只需要维护前面有多少个\(1\)。

　　\(f_i\)表示执行后面\(i\)_{$n$的指令，前面$g_{i,0}$}\(g_{0,f_i}\)全部是\(1\)，\(g_{i,f_i+1}\)是\(0\)。

　　那么如果\(d_i\leq 2f_{i+1}+1\)，那么\(f_i=f_{i+1}+d_i\)。否则\(f_i=f_{i+1}\)。

　　可以发现，第一种情况\(0\)~\(f_i\)之间不会有空洞。

　　询问\(a_i\)时直接判断\(c_{a_i-1}\)是不是比\(f_{a_i+1}\)大。这样直接走到\(f_{a_i+1}+1\)就可以了。

　　时间复杂度：\(O(n)\)

代码

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cstdlib>

#include<ctime>

#include<utility>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int,int> pii;

int n,q;

ll m;

ll d[500010];

ll c[500010];

ll f[500010];

void rd(int &s)

{

	int c;

	while((c=getchar())<'0'||c>'9');

	s=c-'0';

	while((c=getchar())>='0'&&c<='9')

		s=s*10+c-'0';

}

void rd(ll &s)

{

	int c;

	while((c=getchar())<'0'||c>'9');

	s=c-'0';

	while((c=getchar())>='0'&&c<='9')

		s=s*10+c-'0';

}

int abs(int x)

{

	return x>0?x:-x;

}

void yes()

{

	putchar('Y');

	putchar('E');

	putchar('S');

	putchar('\n');

}

void no()

{

	putchar('N');

	putchar('O');

	putchar('\n');

}

int main()

{

#ifdef DEBUG

	freopen("a.in","r",stdin);

	freopen("a.out","w",stdout);

#endif

	scanf("%d%lld",&n,&m);

	int i;

	ll x;

	c[0]=m;

	for(i=1;i<=n;i++)

	{

		rd(d[i]);

		c[i]=min(c[i-1],abs(c[i-1]-d[i]));

	}

	f[n+1]=0;

	for(i=n;i>=1;i--)

	{

		f[i]=f[i+1];

		if(d[i]<=2*f[i+1]+1)

			f[i]=max(f[i],f[i+1]+d[i]);

	}

	scanf("%d",&q);

	for(i=1;i<=q;i++)

	{

		rd(x);

		if(c[x-1]>f[x+1])

			yes();

		else

			no();

	}

	return 0;

}