全屏网站 功能,天津网站建设渠道,服务器网站备案,沙田镇网站建设公司[ARC072C]Alice in linear land
Description
给定a1...ana_1...a_na1...an和DDD#xff0c;mmm轮询问#xff0c;每轮询问给你一个qqq#xff0c;可以让你任意修改aqa_qaq的值#xff0c;然后从小到大对于每一个iii让Dmin(D,D−ai)Dmin(D,D-a_i)Dmin(D,D−ai)mmm轮询问每轮询问给你一个qqq可以让你任意修改aqa_qaq的值然后从小到大对于每一个iii让Dmin(D,D−ai)Dmin(D,D-a_i)Dmin(D,D−ai)问最后是否能让D0D0D0询问两两独立。
n,m≤5∗105n,m\leq 5*10^5n,m≤5∗105
Solution
若能修改的是第xxx个数显然a1...ax−1a_1...a_{x-1}a1...ax−1操作完之后的DDD与修改成什么无关可以直接预处理出a1...aka_1...a_ka1...ak操作后DDD的值dkd_kdk。
然后对于ax...ana_x...a_nax...an若存在一个数y≤dx−1y\leq d_{x-1}y≤dx−1且yyy在ax...ana_x...a_nax...an操作后不为000则答案为YESYESYES否则为NONONO。 因此现在相当于要求出一个最小的yxy_xyx使得yxy_xyx在ax...ana_x...a_nax...an操作之后不为000。我们设yx1y_{x1}yx1为ax1...ana_{x1}...a_nax1...an操作后不为000的最小的yyy考虑如何用yx1y_{x1}yx1求出yxy_xyx。
当yx1≤ax2y_{x1}\leq \frac{a_x}{2}yx1≤2ax时显然yxyx1y_xy_{x1}yxyx1。当yx1ax2y_{x1} \frac{a_x}{2}yx12ax时显然yxyx1axy_xy_{x1}a_xyxyx1ax。 那么这样做会不会存在一个yx′yxy_xy_xyx′yx也满足条件呢可以发现这是不可能的因为按照定义yx′y_{x}yx′一定由yx1′≥yx1y_{x1}\geq y_{x1}yx1′≥yx1转移过来。 当yx1′≤ax2y_{x1}\leq \frac{a_x}{2}yx1′≤2ax时yx′yx1′,yxyx1,yx≤yx′y_xy_{x1},y_xy_{x1},y_x\leq y_xyx′yx1′,yxyx1,yx≤yx′。当yx1′ax2y_{x1} \frac{a_x}{2}yx1′2ax时yx′yx1′axy_xy_{x1}a_xyx′yx1′ax此时yxy_xyx要么为yx1y_{x1}yx1要么为yx1axy_{x1}a_xyx1ax显然yx≤yx′y_x\leq y_xyx≤yx′。 因此可证得我们从后往前递推得到得必然为最小满足条件的yyy于是预处理出所有后缀的yyy即可O(1)O(1)O(1)回答询问。
时间复杂度O(nm)O(nm)O(nm)。
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 secondusing namespace std;templatetypename Tinline bool upmin(T x,T y) { return yx?xy,1:0; }
templatetypename Tinline bool upmax(T x,T y) { return xy?xy,1:0; }typedef long long ll;
typedef unsigned long long ull;
typedef long double lod;
typedef pairint,int PR;
typedef vectorint VI;const lod eps1e-11;
const lod piacos(-1);
const int oo130;
const ll loo1ll62;
const int mods998244353;
const int MAXN600005;
const int INF0x3f3f3f3f;//1061109567
/*--------------------------------------------------------------------*/
inline int read()
{int f1,x0; char cgetchar();while (c0||c9) { if (c-) f-1; cgetchar(); }while (c0c9) { x(x3)(x1)(c^48); cgetchar(); }return x*f;
}
int a[MAXN],b[MAXN],mn[MAXN];
signed main()
{int nread(),Dread(); b[0]D;for (int i1;in;i) a[i]read(),b[i]min(b[i-1],abs(b[i-1]-a[i]));mn[n1]1;for (int in;i1;i--) mn[i](mn[i1]a[i]/2?mn[i1]:mn[i1]a[i]);int mread();for (int i1;im;i){int xread();puts(b[x-1]mn[x1]?YES:NO);}return 0;
}
