AtCoder Regular Contest 072 E：Alice in linear land

题目传送门：https://arc072.contest.atcoder.jp/tasks/arc072_c

题目翻译

给你一个数组(D)，然后给你一个操作序列(d)，每次操作可以将(D)变成(min(D,|D-d[i]|))。假如这一个操作序列执行完了之后你的(D)变成(0)了，那么就称这个操作序列是合法的。现在有(Q)个询问，每个询问由一个(q[i])表示，问你假如你可以把(d[i])变成任意正整数，你能否将这个操作序列变成不合法的。(N,Qleqslant 5*10^5)

题解

对于单次询问(id)，前(id)步走完之后的位置(pos)是确定的。所以我们只需要判断，是否存在一个位置(x)，使得(posgeqslant x geqslant 1)并且从(x)开始执行(id)到(n)号操作走不到(0)。

我们设(f[i])表示最小的位置(x)在执行了(i)到(n)号操作之后不能走到(0)，初始值显然(f[n+1]=1)。

假设(d[i]geqslant f[i+1]*2)那么走这一步显然不会改变，那么(f[i]=f[i+1])，否则(f[i]=f[i+1]+d[i])。

然后对于每个询问，你直接判断(pos[id-1])是否大于等于(f[id+1])就行了，如果满足那么你就可以使(d[i]=f[id+1]-pos[id-1])并且之后的操作都执行完也不会到(0)。

时间复杂度：(O(n+m))

空间复杂度：(O(n))

代码如下：

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;

const int maxn=5e5+5;

int n,m;
ll f[maxn];
int pos[maxn],d[maxn];

int read() {
	int x=0,f=1;char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
	for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
	return x*f;
}

int main() {
	n=read(),pos[0]=read();
	for(int i=1;i<=n;i++) {
		d[i]=read();
		pos[i]=min(pos[i-1],abs(pos[i-1]-d[i]));
	}
	f[n+1]=1;
	for(int i=n;i;i--) {
		f[i]=f[i+1];
		if(d[i]<f[i]*2)f[i]+=d[i];
	}
	m=read();
	for(int i=1;i<=m;i++) {
		int id=read();
		if(pos[id-1]>=f[id+1])puts("YES");
		else puts("NO");
	}
	return 0;
}