题目大意
有一个人要去直线上
lm
远处的地方，他会依次给他的机器发出
n
个指令。第i个指令为
di
。他的机器收到一个指令
x
后，如果向目的地方向前进xm后比当前离目的地更近，就会向前移动
xm
，否则什么都不会做。
现在，给你
q
个询问，第i个询问为
ai
，问你能不能改变
dai
，使得这个人不能到达目的地。你可以决定把
dai
改成什么数。
n,q≤500000,1≤di≤109
题解
首先我们先算出执行前面
i
个指令后离终点的距离ci
暴力的做法是用DP算出
gi,j
：执行后面
i
~n的指令，离终点的距离为
j
，执行完后能不能到达终点。
然后就会发现一旦出现一个0，后面的
1
就会无意义。（因为可以修改成直接走到0这里）
那么我们只需要维护前面有多少个
1
。
fi表示执行后面
i
~n的指令，前面
gi,0
~
g0,fi
全部是
1
，gi,fi 1是
0
。
那么如果di≤2fi 1 1，那么
fi=fi+1+di
。否则
fi=fi+1
。
可以发现，第一种情况
0
~fi之间不会有空洞。
询问
ai
时直接判断
cai−1
是不是比
fai+1
大。这样直接走到
fai+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;
}
