[??记录]AT2401 [ARC072C] Alice in linear land
command_block
2021-05-11 21:00:04
**题意** ： 维护一个变量 $X$ ，初始值为 $L$。
给出长度为 $n$ 的指令序列 $A$ 。
依次执行 $A_{1\sim n}$ ，对于 $A_i$ ，令 $X\leftarrow \min\big\{|X-A_i|,x\big\}$。
给出 $q$ 次询问，每次给出 $p$ ，允许对 $A_p$ 进行任意修改，判定能否使得 $A$ 执行完成后 $X$ 不为 $0$。
询问之间**独立**。
$n,q\leq 5\times 10^5$ ，时限$\texttt{2s}$。
------------
对于某个操作，可以将操作序列分为 前缀 / 被操作的一个元素 / 后缀 三个部分。
记操作 $A_{1\sim k}$ 执行完后 $X$ 的值为 $X_i$ ，容易预处理。
对于修改 $A_p$ 的操作，先取出 $X_{p-1}$ ，然后通过 $A_p$ ，能（且只能）得到 $[0,X_{p-1}]$ 中的数。
现在问题转化为 ： 对于每个后缀，求出是否存在 $[0,X_{p-1}]$ 中的初始值，使得操作结果不为 $0$。
记 $g_{i,x}$ 表示初始值为 $x$ 时，执行 $A_{i\sim n}$ 会不会得到 $0$。
能列出如下转移 ：
$$
g_{i,x}=
\begin{cases}
g_{i+1,x}&(x\leq A_i/2)\\
g_{i+1,A_i-x}&(A_i/2< x\leq A_i)\\
g_{i+1,x-A_i}&(A_i\leq x)
\end{cases}
$$
整个 $\rm DP$ 的复杂度是 $O(nL)$ ，无法通过。
注意到 $\rm DP$ 的决策是固定的（转移 $\rm DAG$ 是一个内向树），没有“最优化”成分。
这些状态之间的贡献关系并不紧密，尝试对状态进行简化。
我们在询问中需要判定 $g_{p+1,0\sim X_{p-1}}$ 中是否存在 $0$。
可以只关心 $g_{p+1,\_}$ 中最靠前的一个 $0$。
记 $f_i$ 为通过 $A_{i,n}$ 不会变为 $0$ 的最小的数。
有转移 ：
$$
f_i=
\begin{cases}
f_{i+1}&(f_{i+1}\leq A_i/2)\\
f_{i+1}+A_i&(f_{i+1}>A_i/2)
\end{cases}
$$
（不难证明只有最小值会转移到最小值）
复杂度 $O(n)$。
```cpp
#include<algorithm>
#include<cstdio>
#define MaxN 500500
using namespace std;
const int mod=1000000007;
int n,q,x[MaxN],a[MaxN],f[MaxN];
int main()
{
scanf("%d%d",&n,&x[0]);
for (int i=1;i<=n;i++){
scanf("%d",&a[i]);
x[i]=min(x[i-1],x[i-1]>a[i] ? x[i-1]-a[i] : a[i]-x[i-1]);
}
f[n+1]=1;
for (int i=n;i;i--){
}
f[i]=f[i+1]*2>a[i] ? f[i+1]+a[i] : f[i+1];
scanf("%d",&q);
for (int i=1,p;i<=q;i++){
scanf("%d",&p);
puts(x[p-1]>=f[p+1] ? "YES" : "NO");
}
return 0;
}
```