这属于是一道比较简单的套路型数据结构题，我们抛开部分分不谈，直接分析正解。
这里给出的是一种不需要线段树或其他高级数据结构的在线做法，唯一需要的是 ST 表和二分。
对于每一个 $i$，考虑蛇 A 如果要进入 $i$ 的副链并要取得胜利，考虑要满足什么样的条件。
蛇 B 向左不断走到达 $i$ 时，蛇 A 没有完全进入副链。
否则蛇 B 跟着进来，先死的肯定是 A。
蛇 B 从 $i$ 右边某个副链进去，能走的步数一定小于 A 能走的步数。
注意到第二个条件和两蛇长度都无关，首先分析。
假设当前蛇 B 在 $j$ 处（目前轮到 A 进入副链），如果存在一个 $mid\in (i,j]$ 使得 $x_i\leq (j-mid)+x_{mid}$，那么 A 就会输。
所以 A 要赢就要使得 $x_i>\max((j-mid)+x_{mid})$，右侧值对于 $j$ 有单调性，所以我们可以找到最大的 $j$，使得如果 B 在它右侧，那么 A 都会输。
也就是说，我们可以求出一个 $L_i$ 表示，当且仅当 B 头位于 $(i,L_i]$ 时，A 此时进入 $i$ 的副链才能使得条件 $2$ 满足。
这里的求法是先建立 $x_i-i$ 的 ST 表，然后对于每个 $i$ 二分。
同理我们求出 $R_i$ 表示，当且仅当 A 头位于 $[R_i,i)$ 时，B 此时进入 $i$ 的副链才能使得对于 B 必胜的条件来说条件 $2$ 满足。
接下来考虑条件 $1$ 的限制。
在条件 $1$ 中我们假设 B 一直往左走，也就是说 $t$ 秒后 B 的蛇头位置为 $c’=c-t$，再考虑 A 完全进入 $i$ 的副链的时间为第 $i-a+1$ 回合 A 行动之后，所以我们要求 $c-(i-a)\leq i$，也就是 $i\ge \dfrac{c+a}{2}$。
也就是说，只要我们钦定 A 能进入副链的 $i$ 必须落在 $L_0=\max(\dfrac{c+a}{2},b)$ 的右侧，那么条件 $1$ 自然满足。
而判定胜负的方法是：谁先进入一个进入则必胜的副链，谁就赢，所以对于 A 我们就要求出编号最小的进入则必胜的副链。
我们依然采用二分，可以进入的副链区间为 $[L_0,R_0]$，其中 $L_0$ 式子在上面，$R_0=\dfrac{b+c}{2}$ 是相撞位置。
我们要检验 $[L_0,mid]$ 中是否存在一个进入即必胜的副链，对于其中某个 $i$，考虑条件 $2$，当 A 蛇头到达 $i$ 也就是 $i-b$ 回合后，B 蛇头的位置应该是 $c-(i-b)$，根据之前的检验条件，需要 $L_i\ge c-(i-b)$，也就是 $L_i+i\ge c+b$。
所以我们又可以建立 $L_i+i$ 的 ST 表，然后求最大值来检验。
对于 B 最先见到的必胜副链，类似，只不过建立的是 $R_i+i$ 的最小值 ST 表。
综上，我们只使用 ST 表和二分，就在 $O((n+q)\log n)$ 的复杂度内在线地完成了本题。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
| #include <bits/stdc++.h>
using namespace std;
const int MAXN=500010;
int n,q,a,b,c,d,lg[MAXN],h[MAXN],l[MAXN],r[MAXN],st[2][MAXN][22];
int read () {
int res=0;
char c=getchar();
while (c<'0'||c>'9') {c=getchar();}
while (c>='0'&&c<='9') {
res=res*10+c-'0';
c=getchar();
}
return res;
}
inline int querymx (int op,int l,int r) {
int k=lg[r-l+1];
return (st[op][l][k]>st[op][r-(1<<k)+1][k]?st[op][l][k]:
st[op][r-(1<<k)+1][k]);
}
inline int querymn (int op,int l,int r) {
int k=lg[r-l+1];
return (st[op][l][k]<st[op][r-(1<<k)+1][k]?st[op][l][k]:
st[op][r-(1<<k)+1][k]);
}
int main () {
n=read();
q=read();
lg[0]=-1;
for (int i=1;i<=n;i++) {
h[i]=read();
st[0][i][0]=h[i]-i,st[1][i][0]=h[i]+i,lg[i]=lg[i>>1]+1;
}
for (int i=1;i<=20;i++) {
for (int k=1;k+(1<<i)-1<=n;k++) {
st[0][k][i]=(st[0][k][i-1]>st[0][k+(1<<(i-1))][i-1]
?st[0][k][i-1]:st[0][k+(1<<(i-1))][i-1]);
st[1][k][i]=(st[1][k][i-1]>st[1][k+(1<<(i-1))][i-1]
?st[1][k][i-1]:st[1][k+(1<<(i-1))][i-1]);
}
}
for (int i=1;i<=n;i++) {
int xl=i,xr=n;
while (xl<xr) {
int mid=(xl+xr+1)>>1;
if (querymx(0,i+1,mid)+mid>=h[i]) {xr=mid-1;}
else {xl=mid;}
}
l[i]=xl;
}
for (int i=n;i>=1;i--) {
int xl=1,xr=i;
while (xl<xr) {
int mid=(xl+xr)>>1;
if (querymx(1,mid,i-1)-mid>=h[i]) {xl=mid+1;}
else {xr=mid;}
}
r[i]=xl;
}
for (int i=1;i<=n;i++) {
st[0][i][0]=l[i]+i;
st[1][i][0]=r[i]-(n-i+1);
}
for (int i=1;i<=20;i++) {
for (int k=1;k+(1<<i)-1<=n;k++) {
st[0][k][i]=(st[0][k][i-1]>st[0][k+(1<<(i-1))][i-1]
?st[0][k][i-1]:st[0][k+(1<<(i-1))][i-1]);
st[1][k][i]=(st[1][k][i-1]<st[1][k+(1<<(i-1))][i-1]
?st[1][k][i-1]:st[1][k+(1<<(i-1))][i-1]);
}
}
for (int i=1;i<=q;i++) {
a=read();
b=read();
c=read();
d=read();
int xl=max(b,(a+c+1)/2),xr=(b+c)/2,cp=c+b;
int disa=1e9,disb=1e9;
if (querymx(0,xl,xr)>=cp) {
while (xl<xr) {
int mid=(xl+xr)>>1;
if (querymx(0,xl,mid)>=cp) {xr=mid;}
else {xl=mid+1;}
}
disa=xl-b;
}
xl=(b+c+2)/2,xr=min(c,(b+d+1)/2),cp=b+1-(n-c+1);
if (querymn(1,xl,xr)<=cp) {
while (xl<xr) {
int mid=(xl+xr+1)>>1;
if (querymn(1,mid,xr)<=cp) {xl=mid;}
else {xr=mid-1;}
}
disb=c-xl;
}
if (disa==1e9&&disb==1e9) {
if ((b-c)&1) {putchar('B');}
else {putchar('A');}
} else {
if (disa<=disb) {
putchar('A');
} else {
putchar('B');
}
}
putchar('\n');
}
return 0;
}
|