AGC012E 题解

First Post:

Last Update:

远古 AGC 还是比现代 AGC (2023) 好做多了。

首先观察跳跃操作在干什么。容易发现只会跳 次，且每次跳完后的水容量都是确定的，为

然后删掉跳跃操作，发现如果此时容量为 ，那么只能在 的绿洲之间往返，也就是说，以每个点开始，能到的段是一个区间。对每种容量和每个位置处理其能到的区间 ，这里 表示容量为 。

那么”遍历所有绿洲“相当于对每个 ，选出一个位置 ，使得最后 。询问则相当于限制 。

在没有限制时怎么做呢？设 表示用了 的区间，能覆盖的最长前缀为 ，从 转移到 时，找到 且 最大的 ，用 更新 即可。

现在考虑有限制的情形。将 代表的区间删去后，如果还可以使得并为 ，答案就全为 Possible。否则，找到一个没被覆盖的点，将其左边的区间集合设为 ，右边的就是 （这里的 不包括 ）。当存在一个 使得 时，答案就是 Possible ，反之为 Impossible。

因为可能的 均只有 个，状压 DP 和最后的统计答案都可以在 的时间内解决。

我写的代码复杂度瓶颈在于找到每个 和 ，用的是二分，时间复杂度为 ，实际上可以用双指针做到 。

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
#include <bits/stdc++.h>
using namespace std;
template<typename T> inline bool ckmin(T &x,const T &y) { return (x > y) && (x = y);}
template<typename T> inline bool ckmax(T &x,const T &y) { return (x < y) && (x = y);}
const int N = 2e5 + 5,Sz = 1 << 19,Lg = 19;
int n,V,lim;
int x[N];
int ST[Lg][N],lg[N]; // min
int f[Sz],g[Sz];
int L[Lg][N],R[Lg][N];
inline int Qmax(int l,int r) {
	if(l > r) return 0x7f7f7f7f;
	int k = lg[r - l + 1];
	return max(ST[k][l],ST[k][r-(1<<k)+1]);
}
struct BIT {
	int tr[N];
	#define lowbit(x) (x&(-x))
	inline void upd(int x,int v) { for(int i = x;i <= n + 1;i += lowbit(i)) tr[i] += v;}
	inline int Sum(int x) { int res = 0;for(int i = x;i;i ^= lowbit(i)) res += tr[i];return res;}
};
BIT T;
inline void GetLR() {
	lg[0] = -1;
	for(int i = 1;i <= n;i++) ST[0][i] = x[i] - x[i - 1],lg[i] = lg[i >> 1] + 1;
	for(int j = 1;j < lim;j++)
		for(int i = 1;i + (1 << j) - 1 <= n;i++)
			ST[j][i] = max(ST[j - 1][i],ST[j - 1][i + (1 << j - 1)]);
	for(int t = 0;t < lim;t++) {
		int nv = V >> t;
		for(int i = 1;i <= n;i++) {
			int lef = 2,rig = i + 1;
			while(lef < rig) {
				int mid = lef + rig >> 1;
				if(Qmax(mid,i) <= nv) rig = mid;
				else lef = mid + 1;
			}
			L[t][i] = lef - 1;
			lef = i;rig = n;
			while(lef < rig) {
				int mid = lef + rig + 1 >> 1;
				if(Qmax(i + 1,mid) <= nv) lef = mid;
				else rig = mid - 1;
			}
			R[t][i] = lef;
		}
	}
}
int dat[Lg][N];
inline void DP() {
	for(int t = 0;t < lim;t++) {
		for(int i = 1;i <= n;i++) ckmax(dat[t][L[t][i]],R[t][i]);
		dat[t][0] = 0;
		for(int i = 1;i <= n;i++) ckmax(dat[t][i],dat[t][i - 1]);
	}
	f[0] = 0;
	for(int S = 0;S < (1 << lim);++S) 
		for(int i = 0;i < lim;i++) if((~S >> i) & 1) 
			ckmax(f[S | (1 << i)],max(f[S],dat[i][f[S] + 1]));
	for(int t = 0;t < lim;t++) {
		for(int i = 0;i <= n + 1;i++) dat[t][i] = n + 1;
		for(int i = 1;i <= n;i++) ckmin(dat[t][R[t][i]],L[t][i]);
		for(int i = n;i >= 1;i--) ckmin(dat[t][i],dat[t][i + 1]);
	}
	for(int i = 0;i < (1 << lim);i++) g[i] = n + 1;
	for(int S = 0;S < (1 << lim);++S)
		for(int i = 0;i < lim;i++) if((~S >> i) & 1)
			ckmin(g[S | (1 << i)],min(g[S],dat[i][g[S] - 1]));
}
vector<int> Cs[N],Qs[N];
int ans[N];
int main() {
	cin >> n >> V;lim = __lg(V) + 2;
	for(int i = 1;i <= n;i++) cin >> x[i];
	GetLR();DP();
	if(f[(1 << lim) - 1 - 1] >= n) {
		for(int i = 1;i <= n;i++) puts("Possible");
		return 0;
	}
	for(int S = 0;S < (1 << lim);++S) 
		if((~S & 1)) {
			int tl = f[S],tr = g[(1 << lim) - 1 - 1 - S];
			Cs[tl].push_back(tr);
		}
	for(int i = 1;i <= n;i++) Qs[L[0][i] - 1].push_back(i);
	for(int i = n;i >= 0;i--) {
		for(auto j : Cs[i]) T.upd(j,1);
		for(auto id : Qs[i])
			ans[id] = T.Sum(R[0][id] + 1) > 0;
	}
	for(int i = 1;i <= n;i++)
		if(ans[i]) puts("Possible");
		else puts("Impossible");
	return 0;
}
≡