CF1913D. Array Collapse
Lu_xZ
·
·
题解
D. Array Collapse
考虑分治。
设 f[l, r]，为区间 [l, r] 能够通过操作得到的子序列数。
设 [l, r] 内最小元素的下标为 p。
如果只考虑 [l, r] 内部的所有情况，因为无论怎么操作 a[p] 都无法被删除，所以有 f[l][r] = f[l][p - 1] \cdot f[p + 1][r]。
考虑外部元素对 f[l][r] 的贡献。
显然，任意一个比 a[p] 大的数都不能使 [l,r] 内有新的子序列出现。
如果 \exists i < l，a[i] < a[p]，那么我们可以把 [l,p] 删掉，剩下 [p + 1, r]，新贡献为 f[p + 1][r]。
如果 \exists j > r，a[j] < a[p]，那么我们可以把 [p,r] 删掉，剩下 [l, p - 1]，新贡献为 f[l][p - 1]。
如果上述 i,j 都存在，我们发现两者重复计算了 [l,r] 全部删掉的方案，则 f[l][r] 减一。
考虑递归边界。
如果 l > r，只存在空集这一种方案。
如果 l = r 且左右两边至少有一个小于 a[l] 的元素，则有 \phi 和 a[l] 两种，否则只有 a[l] 一种。
code
其中 f[i][j] 存的是 [i, i + 2^j - 1] 内最小元素的位置。
```c++
void init() {
for(int i = 1; i <= n; ++ i) f[i][0] = i;
for(int j = 1; j < 20; ++ j) {
for(int i = 1; i + (1 << j) - 1 <= n; ++ i) {
if(a[f[i][j - 1]] < a[f[i + (1 << j - 1)][j - 1]]) f[i][j] = f[i][j - 1];
else f[i][j] = f[i + (1 << j - 1)][j - 1];
}
}
}
int get_pos(int l, int r) {
int len = log2l(r - l + 1);
if(a[f[l][len]] < a[f[r - (1 << len) + 1][len]]) return f[l][len];
else return f[r - (1 << len) + 1][len];
}
ll get_val(int l, int r, bool L_less, bool R_less) {
if(l > r) return 1;
if(l == r && (L_less || R_less)) return 2;
if(l == r) return 1;
int p = get_pos(l, r);
ll left = get_val(l, p - 1, L_less, true);
ll right = get_val(p + 1, r, true, R_less);
ll ret = left * right % P;
if(L_less) ret += right;
if(R_less) ret += left;
if(L_less && R_less) -- ret;
return (ret % P + P) % P;
}
void solve() {
cin >> n;
for(int i = 1; i <= n; ++ i) cin >> a[i];
init();
cout << get_val(1, n, 0, 0) << '\n';
}
```