[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;
}