好久之前模拟赛就考过的题，今天才写）
首先发现我们跳跃的次数只有 \(\log V\) 次，我们设跳了 \(i\) 次后的时刻为第 \(i\) 时刻，且最后一个时刻为 \(t\)。发现每一时刻，我们能够到达的绿洲形成了若干个连续段。不难发现，当时刻 \(0\) 的时候连续段数量大于 \(t + 1\) 时一定全部都无法到达。而对于这每一个连续段，答案一定相等。
那么我们只需要对 \(O(\log V)\) 个位置找出答案即可。考虑如何求答案。
首先发现我们要到达的就是一个前缀加一个后缀，而每一时刻要不然在前缀要不然在后缀，那么我们可以设 DP \(pre_S, suf_S\) 表示如果在 \(S\) 这个时刻集合内都在前缀 / 后缀，那么能覆盖的最长前缀 / 最长后缀是多少。直接转移即可。注意到虽然我们不一定是按顺序从左往右访问，但是由于时刻集合的转移本身就没有顺序，所以是可以覆盖到所有情况的。
总时间复杂度 \(O((n + V) \log V)\)。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
int n, v, t;
int x[MAXN];
int L[22][MAXN], R[22][MAXN];
int pre[1 << 19], suf[1 << 19];
void chkmax(int &a, int b) { a = max(a, b); }
void chkmin(int &a, int b) { a = min(a, b); }
int main() {
scanf("%d%d", &n, &v);
t = __lg(v) + 1;
for (int i = 1; i <= n; i++) {
scanf("%d", &x[i]);
}
for (int j = 0; j <= t; j++) {
L[j][1] = 1;
for (int i = 2; i <= n; i++) {
if (x[i] - x[i - 1] <= (v >> j)) L[j][i] = L[j][i - 1];
else L[j][i] = i;
}
R[j][n] = n;
for (int i = n - 1; i >= 1; i--) {
if (x[i + 1] - x[i] <= (v >> j)) R[j][i] = R[j][i + 1];
else R[j][i] = i;
}
}
memset(suf, 0x3f, sizeof suf);
suf[0] = n + 1;
int cnt = 0, now = R[0][1];
while (now < n) now = R[0][now + 1], cnt++;
if (cnt > t) {
for (int i = 1; i <= n; i++) {
printf("Impossible\n");
}
return 0;
}
for (int s = 0; s < (1 << t); s++) {
for (int i = 1; i <= t; i++) if (!(s >> (i - 1) & 1)) {
chkmax(pre[s | 1 << (i - 1)], R[i][min(pre[s] + 1, n)]);
chkmin(suf[s | 1 << (i - 1)], L[i][max(suf[s] - 1, 1)]);
}
}
int S = (1 << t) - 1;
for (int l = 1, r; l <= n; l = r + 1) {
r = R[0][l];
bool flag = false;
for (int s = 0; s < (1 << t); s++) {
if (pre[s] >= l - 1 && suf[S ^ s] <= r + 1) {
flag = true;
break;
}
}
for (int i = l; i <= r; i++) {
if (flag) printf("Possible\n");
else printf("Impossible\n");
}
}
return 0;
}