一根数轴上分布着nn个点，有一个人会在上面移动。首先会选择一个点作为起点，并有一个初始的能力值vv，然后每次可以执行下面的一种操作：

  • 移动到一个相邻的点,并且该节点距离当前点不超过vv
  • 跳跃到任意一个点,前提是v>0v > 0,但是能力值会变为⌊v2⌋\lfloor\frac v2\rfloor

你需要求出对于每一个点作为起点，是否能够到达所有的点

n,v≤2×105n, v\le 2\times10^5

AGC012E

Solution

这道题不难

首先，不同的能力值只有log\log个，即最多只有log\log层。于是可以对每种不同的能力值，处理出一些可以相互到达的连续段

问题就转化成，每种能力值最多取一根线段，能否把[1,n][1, n]覆盖

先考虑除了vv那一层的线段，设f[S],g[S]f[S], g[S]表示取了SS集合的层， 能覆盖的最大前缀、最大后缀，随便转移

考虑vv那一层的每个线段[l,r][l, r]，若存在一个集合SS，满足l−1≤f[S]l- 1\le f[S]且g[ALL⊕j]≤r+1g[ALL \oplus j]\le r + 1，那么[l,r][l, r]中的数都合法

Code

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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back
#define DEBUG(x) cout << #x << " = " << x << endl;

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

inline void proc_status ()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Maxn = 2e5 + 100;
const int Maxm = 20 + 5;
const int Maxs = (1 << 20) + 100;

int N, V, Log;
int A[Maxn];

int L[Maxm][Maxn], R[Maxm][Maxn];
int Next[Maxn];

inline void get_seg ()
{
	for (int i = 0; i <= Log; ++i)
	{
		int v = V >> i;
//		DEBUG (v);
		for (int j = N; j >= 1; --j)
		{
			int p = upper_bound (A + 1, A + N + 1, A[j] + v) - A - 1;
			Next[j] = 0;
			Next[j] = max (Next[p], j);
		}
		for (int l = 1, r = 0; l <= N; l = r + 1)
		{
			r = Next[l];
			L[i][++L[i][0]] = l, R[i][++R[i][0]] = r;
		}
	}
}

int f[Maxs], g[Maxs];

inline void get_f ()
{
	int ALL = (1 << Log) - 1;
	for (int i = 0; i <= ALL; ++i)
	{
		int preR = f[i];
		for (int j = 1; j <= Log; ++j)
		{
			if (i & (1 << (j - 1))) continue;
			int x = upper_bound (L[j] + 1, L[j] + L[j][0] + 1, preR + 1) - L[j] - 1;
			int nowR = max (preR, R[j][x]);
			Chkmax (f[i | (1 << (j - 1))], nowR);
		}
	}
}

inline void get_g ()
{
	int ALL = (1 << Log) - 1;
	for (int i = 0; i <= ALL; ++i) g[i] = N + 1;
	for (int i = 0; i <= ALL; ++i)
	{
		int preL = g[i];
		for (int j = 1; j <= Log; ++j)
		{
			if (i & (1 << (j - 1))) continue;
			int x = lower_bound (R[j] + 1, R[j] + R[j][0] + 1, preL - 1) - R[j];
			int nowL = min (preL, L[j][x]);
			Chkmin (g[i | (1 << (j - 1))], nowL);
		}
	}
}

inline void Solve ()
{
	get_seg ();
	get_f ();
	get_g ();

	if (L[0][0] > Log + 3) { for (int i = 1; i <= N; ++i) puts("Impossible"); return ; }

	int ALL = (1 << Log) - 1;
	for (int i = 1; i <= L[0][0]; ++i)
	{
		int l = L[0][i], r = R[0][i], fl = 0;
		for (int j = 0; j <= ALL; ++j)
			if (l - 1 <= f[j] && g[ALL ^ j] <= r + 1)
			{
				fl = 1;
				break;
			}
		if (fl) for (int j = l; j <= r; ++j) puts("Possible");
		else for (int j = l; j <= r; ++j) puts("Impossible");
	}
}

inline void Input ()
{
	N = read<int>(), V = read<int>(), Log = log2(V) + 1;
	for (int i = 1; i <= N; ++i) A[i] = read<int>();
}

int main()
{

#ifdef hk_cnyali
	freopen("E.in", "r", stdin);
	freopen("E.out", "w", stdout);
#endif

	Input ();
	Solve ();

	return 0;
}