AT_arc072_c [ARC072E] Alice in linear land 题解

题意

有一个数轴，终点为原点。一个机器人位于 $D$，有 $n$ 条指令，对第 $i$ 条指令机器人会向终点移动 $d_i$ 距离，若移动后距离变大则不移动，意思是可能冲过，但是若距离变小就可以过去。

给出 $m$ 个询问，第 $i$ 次询问允许将 $d_{q_i}$ 修改为任意整数（仅当前询问生效）。问是否存在修改方案使机器人不能走到终点。

题解

记 $dis_i$ 表示不修改前 $i$ 个操作情况下，当前能走动哪。那么对于一次可以修改 $d_x$ 的询问，若存在一个 $y\leq d_{x-1}$ 使得 $y$ 在经过 $i+1$ 到 $n$ 的操作后没到 $0$ 则有解，否则无解。所以考虑求出最小使得走完后面操作不为 $0$ 的距离，记 $mn_i$ 表示最小走完 $i$ 到 $n$ 的操作之后不为 $0$ 的距离，倒着 dp 即可：

1. 当 $mn_{i+1}\leq\frac{d_i}{2}$，有 $mn_i=mn_{i+1}$。因为这种情况肯定会直接冲过，但是冲过 $d_i-mn_{i+1}\geq mn{i+1}$ 故不会这样走，这样 $mn_i$ 取到了下限。
2. 当 $mn_{i+1}\gt\frac{d_i}{2}$，有 $mn_i=mn_{i+1}+d_i$。分类讨论一下，若这一步是冲过的，那么 $m_i=d_i-mn_{i+1}\lt mn_{i+1}$ 所以不可能；若没动，那么 $mn_i=mn_{i+1}$ 这时候若直接冲过 $d_i-mn_{i+1}\lt mn_{i+1}$ 不可能，或者直接走过去 $mn_{i+1}-d_{i+1}\lt mn_{i+1}$ 所以也不可能；所以只能是直接走过去的情况。

#include<bits/stdc++.h>
// #define ONLINE_JUDGE
#define INPUT_DATA_TYPE int
#define OUTPUT_DATA_TYPE int
inline __attribute((always_inline)) INPUT_DATA_TYPE read(){register INPUT_DATA_TYPE x=0;register char f=0,c=getchar();while(c<'0'||'9'<c)f=(c=='-'),c=getchar();while('0'<=c&&c<='9')x=(x<<3)+(x<<1)+(c&15),c=getchar();return f?-x:x;}void print(OUTPUT_DATA_TYPE x){if(x<0)x=-x,putchar('-');if(x>9)print(x/10);putchar(x%10^48);return;}

int mnD[500010],dis[500010],d[500010];

int abss(int x){return x<0?-x:x;}

int main(){
	#ifndef ONLINE_JUDGE
	freopen("name.in", "r", stdin);
	freopen("name.out", "w", stdout);
	#endif

    register int i;
    int n=read();
    dis[0]=read();
    for(i=1;i<=n;++i){
        d[i]=read();
        dis[i]=std::min(abss(dis[i-1]-d[i]),dis[i-1]);
    }
    mnD[n+1]=1;
    for(i=n;i;--i){
        if(d[i]/2>=mnD[i+1]) mnD[i]=mnD[i+1];
        else mnD[i]=mnD[i+1]+d[i];
    }

    int q=read();
    while(q--){
        i=read();
        puts(dis[i-1]>=mnD[i+1]?"YES":"NO");
    }

	#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	#endif
    return 0;
}