题目

瑟瑟发抖,这竟然只是个蓝题

题意大概就是初始在\(0\),要到坐标为\(D\)的地方去,有\(n\)条指令,第\(i\)条为\(d_i\)。当收到一条指令\(x\)后,如果向\(D\)方向走\(x\)后距离\(D\)更近,那么就走;否则就停留在原地。

现在有\(Q\)次询问,第\(i\)次询问为\(q_i\),问能不能仅改变\(d_{q_i}\),使得其不能到达\(D\)

考虑一个暴力,设\(g_{i,j}\)表示当\(D=j\)时,只使用后\(i\)次操作能否到达\(j\)

考虑如何求出\(g_{i,j}\)

转移大概长这样

\[g_{i,j}=\left\{\begin{matrix}g_{i+1,j-d_i} & d_i\leq j\\g_{i+1,d_i-j} & j<d_i<2j\\ g_{i+1,j}&d_i\geq 2j\end{matrix}\right.\]

就是当\(d_i\leq j\)的时候,只能到达距离目标\(j-d_i\)的地方

\(j<d_i<2j\),我们会走过\(j\)点,到达距离目标\(d_i-j\)的地方,这个时候翻转一下正方向即可

\(d_i>2j\)的时候,显然走过去的点距离目标更远,于是直接不走

我们再处理出一个数组\(pos_i\)表示第\(i\)次操作后距离\(D\)点的距离

当遇到一个询问\(q_i\)的时候,如果我们要改变\(d_{q_i}\),那么可能我们只能改变为\(0\)\(2\times pos_{i-1}\)的数,只有这些才是有效移动

进行有效移动后距离目标点的距离也只可能从\(pos_{i-1}\)\(0\),所以只需要\(g_{q_i+1,0}\)\(g_{q_i+1,pos_{i-1}}\)里有一个是\(0\),那么我们就可以走这个距离,之后就不可能走到目标点了

这样复杂度是\(O(nD)\)的,显然过不了

考虑一下如何不求\(g\)数组,而直接高效询问

发现我们一次询问只关注\(g_{q_i+1}\)的前\(pos_{i-1}\)项有没有一个\(0\),显然一个靠前的\(0\)能影响更多的询问

所以我们如果知道使得\(g_{i,j}=0\)最小的\(j\)在哪里,也能快速回答询问

\(dp_i\)表示使得\(g_{i,j}=0\)最小的\(j\),考虑求出\(dp\)数组

根据上面\(g\)数组的转移,尝试反推\(dp\)数组的转移

\(d_i\geq 2\times dp_{i+1}\)时,\(dp_{i}=dp_{i+1}\)。这对应了上面的第三个转移

\(dp_{i+1}=d_i-j\),即\(dp_{i}=d_i-dp_{i+1}\)时,需要满足\(d_i-dp_{i+1}<d_i<2(d_i-dp_{i+1})\),即\(d_i>2\times dp_{i+1}\)时。这对应了第二个转移。

\(dp_{i+1}=j-d_i\),即\(dp_i=dp_{i+1}+d_i\)时,需要满足\(d_i\leq dp_{i+1}+d_i\),这显然成立。这对应了上面第三个转移。

根据条件取上面三个转移的最小值即可,回答询问的时候只需要判断一下\(dp_{q_i+1}\)\(pos_{q_{i-1}}\)的大小关系即可

代码

#include<bits/stdc++.h>
#define re register
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
inline int read() {
    char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
const int maxn=5e5+5;
int d[maxn],dp[maxn],pos[maxn];
int n,D,Q;
inline int ABS(int x) {return x>=0?x:-x;}
int main() {
    n=read();D=read();dp[n+1]=1;
    for(re int i=1;i<=n;i++) d[i]=read();
    for(re int i=n;i;--i) {
        if(d[i]>=2*dp[i+1]) {
            dp[i]=dp[i+1];
            if(d[i]>2*dp[i+1]) dp[i]=min(dp[i],d[i]-dp[i+1]);
        }
        else dp[i]=dp[i+1]+d[i];
    }
    pos[0]=D;
    for(re int i=1;i<=n;i++) pos[i]=min(ABS(pos[i-1]-d[i]),pos[i-1]);
    Q=read();int x;
    while(Q--) x=read(),puts(dp[x+1]<=pos[x-1]?"YES":"NO");
    return 0;
}
02-11 02:29