[ARC072E] Alice in linear land

首先，一个 trivial 的想法是记 \(f_i\) 表示第 \(i\) 步前离终点的距离，于是 \(f_i=\min\Big(f_{j-1},|f_{j-1}-d_i|\Big)\)。

然后，我们设 \(f_i'\) 表示在修改第 \(i\) 步后，此时离终点的距离。明显，\(f_i'\) 可以为任意不大于 \(f_i\) 的值，因为此时的 \(d_i'\) 可以任意取值。

于是问题转换为是否存在一个 \(f_i'\)，满足按照剩余的操作后缀执行后不会到达 0（可以把它看作是在自动姬上按照一堆指令执行后不会到达 0 状态）。

因为 \(f_i'\) 有其上界，所以我们只需知道要使当前后缀不为 0 ，所需的最小 \(f_i'\)，然后将其与 \(f_i\) 比较即可。考虑设 \(g_i\) 表示若不执行操作 \(i\)，然后再执行其剩余操作后，使得终止位置不在 0 的最小 \(f_i'\)。则最终只需比较 \(f_{i-1}\) 与 \(g_i\) 即可。

考虑倒着转移 \(g\)。这个只需要分类讨论，处理 \(d_i\leq g_i,d_i\geq 2g_i,g_i<d_i<2g_i\) 三种情形即可。

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

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=5e5+100;
int n,m,x;
int d[N],f[N];
inline int read(){
    char c=getchar();int f=1,x=0;
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
LL g[N];
int main(){
    n=read();
    f[0]=read();
    for(int i=1;i<=n;i++){
		d[i]=read();
		f[i]=min(f[i-1],abs(f[i-1]-d[i]));
	}
    g[n]=1;
    for(int i=n;i;i--){
        if(d[i]<=g[i]) g[i-1]=g[i]+d[i];
        else if(d[i]>=2*g[i]) g[i-1]=g[i];
        else g[i-1]=g[i]+d[i];
    }
//  for(int i=0;i<=n;i++) printf("%d ",f[i]);
//	printf("\n");
//  for(int i=0;i<=n;i++) printf("%d ",g[i]);
//	printf("\n");
    m=read();
	while(m--){
		x=read();
		if(f[x-1]>=g[x]) printf("YES\n");
		else printf("NO\n");
	}
    return 0;
}