[ARC072E] Alice in linear land

VIII.[ARC072E] Alice in linear land

首先，一个trivial的想法是记 (f_i) 表示第 (i) 步前离终点的距离，于是 (f_i=minBig(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_ileq g_i,d_igeq 2g_i,g_i<d_i<2g_i) 三种情形即可。

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

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,q,d[500100],f[500100];
ll g[500100];
int main(){
	scanf("%d%d",&n,&f[0]);
	for(int i=1;i<=n;i++)scanf("%d",&d[i]),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]);puts("");
//	for(int i=0;i<=n;i++)printf("%d ",g[i]);puts("");
	scanf("%d",&q);for(int i=1,x;i<=q;i++)scanf("%d",&x),puts(f[x-1]>=g[x]?"YES":"NO");
	return 0;
}