[ARC072C]Alice in linear land

Description

给定 a 1 . . . a n a_1...a_n a1​...an​和 D D D， m m m轮询问，每轮询问给你一个 q q q，可以让你任意修改 a q a_q aq​的值，然后从小到大对于每一个 i i i让 D = m i n ( D , D − a i ) D=min(D,D-a_i) D=min(D,D−ai​)，问最后是否能让 D = 0 D=0 D=0，询问两两独立。

n , m ≤ 5 ∗ 1 0 5 n,m\leq 5*10^5 n,m≤5∗105

Solution

若能修改的是第 x x x个数，显然 a 1 . . . a x − 1 a_1...a_{x-1} a1​...ax−1​操作完之后的 D D D与修改成什么无关，可以直接预处理出 a 1 . . . a k a_1...a_k a1​...ak​操作后 D D D的值 d k d_k dk​。

然后对于 a x . . . a n a_x...a_n ax​...an​，若存在一个数 y ≤ d x − 1 y\leq d_{x-1} y≤dx−1​，且 y y y在 a x . . . a n a_x...a_n ax​...an​操作后不为 0 0 0，则答案为 Y E S YES YES，否则为 N O NO NO。

---

因此现在相当于要求出一个最小的 y x y_x yx​，使得 y x y_x yx​在 a x . . . a n a_x...a_n ax​...an​操作之后不为 0 0 0。我们设 y x + 1 y_{x+1} yx+1​为 a x + 1... a n a_x+1...a_n ax​+1...an​操作后不为 0 0 0的最小的 y y y，考虑如何用 y x + 1 y_{x+1} yx+1​求出 y x y_x yx​。

• 当 y x + 1 ≤ a x 2 y_{x+1}\leq \frac{a_x}{2} yx+1​≤2ax​​时，显然 y x = y x + 1 y_x=y_{x+1} yx​=yx+1​。
• 当 y x + 1 > a x 2 y_{x+1}> \frac{a_x}{2} yx+1​>2ax​​时，显然 y x = y x + 1 + a x y_x=y_{x+1}+a_x yx​=yx+1​+ax​。

那么这样做会不会存在一个 y x ′ < y x y'_x<y_x yx′​<yx​也满足条件呢？可以发现这是不可能的，因为按照定义 y x ′ y'_{x} yx′​一定由 y x + 1 ′ ≥ y x + 1 y'_{x+1}\geq y_{x+1} yx+1′​≥yx+1​转移过来。

• 当 y x + 1 ′ ≤ a x 2 y'_{x+1}\leq \frac{a_x}{2} yx+1′​≤2ax​​时， y x ′ = y x + 1 ′ , y x = y x + 1 , y x ≤ y x ′ y'_x=y'_{x+1},y_x=y_{x+1},y_x\leq y'_x yx′​=yx+1′​,yx​=yx+1​,yx​≤yx′​。
• 当 y x + 1 ′ > a x 2 y'_{x+1}> \frac{a_x}{2} yx+1′​>2ax​​时， y x ′ = y x + 1 ′ + a x y'_x=y'_{x+1}+a_x yx′​=yx+1′​+ax​，此时 y x y_x yx​要么为 y x + 1 y_{x+1} yx+1​，要么为 y x + 1 + a x y_{x+1}+a_x yx+1​+ax​，显然 y x ≤ y x ′ y_x\leq y'_x yx​≤yx′​。

因此可证得，我们从后往前递推得到得必然为最小满足条件的 y y y，于是预处理出所有后缀的 y y y，即可 O ( 1 ) O(1) O(1)回答询问。

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

Code

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <cassert>
#include <string.h>
//#include <unordered_set>
//#include <unordered_map>
//#include <bits/stdc++.h>

#define MP(A,B) make_pair(A,B)
#define PB(A) push_back(A)
#define SIZE(A) ((int)A.size())
#define LEN(A) ((int)A.length())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define fi first
#define se second

using namespace std;

template<typename T>inline bool upmin(T &x,T y) { return y<x?x=y,1:0; }
template<typename T>inline bool upmax(T &x,T y) { return x<y?x=y,1:0; }

typedef long long ll;
typedef unsigned long long ull;
typedef long double lod;
typedef pair<int,int> PR;
typedef vector<int> VI;

const lod eps=1e-11;
const lod pi=acos(-1);
const int oo=1<<30;
const ll loo=1ll<<62;
const int mods=998244353;
const int MAXN=600005;
const int INF=0x3f3f3f3f;//1061109567
/*--------------------------------------------------------------------*/
inline int read()
{
	int f=1,x=0; char c=getchar();
	while (c<'0'||c>'9') { if (c=='-') f=-1; c=getchar(); }
	while (c>='0'&&c<='9') { x=(x<<3)+(x<<1)+(c^48); c=getchar(); }
	return x*f;
}
int a[MAXN],b[MAXN],mn[MAXN];
signed main()
{
	int n=read(),D=read(); b[0]=D;
	for (int i=1;i<=n;i++) a[i]=read(),b[i]=min(b[i-1],abs(b[i-1]-a[i]));
	mn[n+1]=1;
	for (int i=n;i>=1;i--) mn[i]=(mn[i+1]<=a[i]/2?mn[i+1]:mn[i+1]+a[i]);
	int m=read();
	for (int i=1;i<=m;i++)
	{
		int x=read();
		puts(b[x-1]>=mn[x+1]?"YES":"NO");
	}
	return 0;
}