题解：CF2159D2 Inverse Minimum Partition (Hard Version)
wangsiyuan2022
·
·
题解
我是小菜鸡 Div.2 rk60+
通过模拟我们可以发现一下几个性质。
我们设 a 的值域为 V。
-
- 任意 f[l, r] 不大于 2\log(V)≤128。
- 总有一个最优解，只使用成本最多为 3 的子数组。
定义 g_{i, r} 表示，以 r 为右端点，使用 1 次成本为 i 的子数组能到达的最左边的位置，由于性质3，1≤i≤3，可以使用线段树或者 RMQ + 二分求出 g 数组。
设 dp_{i, r} 表示右端点为 r 的时候，代价 f[l,r] ≤ i 的最小 l，由于性质 2，i \leq 128，我们有转移。
根据性质 1 的单调性我们可以知道，最终答案
## code
```cpp
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
#define ll long long
const int N = 400005;
const int mod = 1000000007;
const int INF = 0x3f3f3f3f;
int T, n;
ll a[N], mn[N][20];
int lg[N], st[4][N][20], f[130];
int st_query(int k, int l, int r) {
int len = lg[r - l + 1];
return min(st[k][l][len], st[k][r - (1 << len) + 1][len]);
}
ll get(int l, int r) {
int len = lg[r - l + 1];
return min(mn[l][len], mn[r - (1 << len) + 1][len]);
}
int binary(int R, ll x) { // 1 ~ r 范围内使得 min[i ~ r] >= x 大最小的i
int l = 1, r = R;
while (l <= r) {
int mid = (l + r) >> 1;
if (get(mid, R) < x) l = mid + 1;
else r = mid - 1;
}
return l;
}
int main() {
for (int i = 2; i < N; i++) lg[i] = lg[i >> 1] + 1;
int T;
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
int t = 0;
for (int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
}
for (int i = 1; i <= n; i++) mn[i][0] = a[i];
for (int i = 1; (1 << i) <= n; i++) {
for (int j = 1; j + (1 << i) - 1 <= n; j++) {
mn[j][i] = min(mn[j][i - 1], mn[j + (1 << (i - 1))][i - 1]);
}
}
// get the array of L
for (int r = 1; r <= n; r++) {
for (int i = 1; i <= 3; i++) {
st[i][r][0] = binary(r, (a[r] + i - 1) / i);
}
}
for (int k = 1; k <= 3; k++) {
for (int i = 1; (1 << i) <= n; i++) {
for (int j = 1; j + (1 << i) - 1 <= n; j++) {
st[k][j][i] = min(st[k][j][i - 1], st[k][j + (1 << (i - 1))][i - 1]);
}
}
}
ll ans = 0;
for (int r = 1; r <= n; r++) {
f[0] = r + 1;
for (int i = 1; i <= 128; i++) {
f[i] = INF;
for (int k = 1; k <= min(i, 3); k++) {
f[i] = min(st_query(k, max(f[i - k] - 1, 1), r), f[i]);
}
}
for (int i = 1; i <= 128; i++) {
ans += (f[i - 1] - f[i]) * i;
}
}
printf("%lld\n", ans);
}
return 0;
}
```