题解：AT_arc207_c [ARC207C] Combine to Make Non-decreasing
ZnPdCo
·
·
题解
来点简单好写做法。
考虑维护 g_i 表示 1\sim i 的最多段数，f_i 表示在将 1\sim i 划分为最多段的情况下，最后一段最小能是多少。
从小到大扫描 i，设 t_{j} 表示 a_j\operatorname{or}a_{j+1}\operatorname{or}\cdots\operatorname{or} a_i 的值。这个可以每次将 j 从大到小枚举暴力更新直到 t_j 的值不变，那么此时比 j 更前的 t_j 显然也不会变了，因为一个数最多只能被更新 \log A 次，所以均摊下来暴力的复杂度是正确的。
我们现在要划分一个段 [x,i]，转移就是 f_i\gets t_x,g_i\gets g_{x-1}+1。考虑贪心找到这个 x，显然是选择一个最大的转移点 x 满足 f_{x-1}\le t_x 是最优的，因为 g_x 具有单调性，x 越大，g 越大，同时 t_x 越小，所以贪心是对的。
综上，复杂度 $O(n\log A)$。
```cpp
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 200010;
int n, a[N], f[N], g[N], t[N];
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int x = 1;
for (int i = 1; i <= n; i++) {
for (int j = i; j >= 1; j--) {
if ((t[j] | a[i]) == t[j]) break;
t[j] |= a[i];
if (f[j - 1] <= t[j]) x = max(x, j);
}
f[i] = t[x];
g[i] = g[x - 1] + 1;
}
cout << g[n] << endl;
}
```