A
B
C
D
首先考虑：对于 \(a\) 数组的任意一段区间 \([l,r]\)，都总有一种办法可以让这些数字全部变成 \(0\)。
构造：
- 若 \([l,r]\) 一段区间全部为 \(0\)，则已经达成条件。
- 否则，将所有 \(x\in [l,r]\cap \textbf{N}_+\) 的 \(a_x\neq0\)，都让 \([x,x]\) 这一段区间取 \(\text{mex}\)。
但是第二步最坏需要执行区间的长度次操作，太过于慢。所以考虑优化：
- 若 \([l,r]\) 中没有 \(0\)，则对 \([l,r]\) 整体执行一次 \(\text{mex}\) 操作，全部变为 \(0\)。
- 若 \([l,r]\) 中有 \(0\)，则对 \([l,r]\) 整体先执行一遍 \(\text{mex}\) 操作，此时 \([l,r]\) 区间中所有元素全部非 \(0\)，所以转化为第一种情况。
然后发现对于一个全 \(0\) 的区间 \([l,r]\)，都可以让这一段区间的所有元素全部变为 \(r-l+1\)。
构造方案：
容易发现，若对于一段序列 \(a\)，满足 \(a\) 中的 \(n\) 个元素分别为 \(0,1,2,\ldots,n-1\)，则对整个 \(a\) 执行一次 \(\text{mex}\) 之后，\(a\) 中的所有元素变为 \(n,n,n,\ldots,n\)。
所以说，若想要把 \([l,r]\) 一段区间的值全部变为 \(r-l+1\)，则若当前执行到了前缀 \([l,i]\)，则只需要将 \([l,i-1]\) 的值变为 \(1,2,3,\ldots,i-l\) 然后将 \(a_i\) 变为 \(0\)，对 \([l,i]\) 这个区间整体做 \(\text{mex}\) 操作即可让 \([l,i]\) 前缀的值全部变为 \(i-l+1\)。
更具体的来说，考虑递归。设当前递归的区间是 \([l,r]\)：
- 若 \(l=r\)：
- 若 \(a_l=0\)，则一次操作区间 \([l,l]\) 让 \(a_l=1\)。
- 若 \(a_l\neq 0\)，则两次操作区间 \([l,l]\)。其中第一次 \(a_l=0\)，第二次即转化为第一种 \(a_l=0\) 的情况。
- 若 \(l\neq r\)：
- 先让 \([l,r]\) 区间全部归 \(0\)。
- 将 \([l+1,r]\) 区间递归处理，此时 \([l,r]\) 区间的值为 \(0,1,2,\ldots,r-l\)。
- 对 \([l,r]\) 区间整体做 \(\text{mex}\) 操作。此时 \([l,r]\) 区间的值是 \(r-l+1,r-l+1,r-l+1,\ldots,r-l+1\)。
- 对 \([l,r-1]\) 整体做 \(\text{mex}\) 操作，此时 \([l,r]\) 区间的值是 \(0,0,0,\ldots,0,r-l+1\)。
- 对 \([l,r-1]\) 区间递归处理，此时 \([l,r]\) 区间的值是 \(0,1,2,\ldots,r-l+1\)。
因此在最坏操作 \(2^{r-l+1}\) 级别次的操作数量下让 \([l,r]\) 区间的值变成了 \(0,1,2,\ldots,r-l+1\)。
最后整体对 \([l,r]\) 再执行一遍 \(\text{mex}\) 操作，\([l,r]\) 区间的值全部变为 \(r-l+1\)，操作执行成功。
现在考虑一种比较简单的方法：对 \([0,n)\) 中的每一个元素 \(a_i\)，都分别钦定其执行操作 / 不执行操作。设当前所有被钦定执行操作的连续下标区间分别为 \([l_1,r_1]\)，\([l_2,r_2]\)，\(\ldots\)，\([l_k,r_k]\)，那么对这 \(k\) 个区间分别执行上面的操作。考虑证明这样做操作的次数一定不会超过 \(5\times 10^5\) 次。
首先计算一段区间 \([l,r]\) 执行上面的操作需要花费的最多 \(\text{mex}\) 覆盖次数。
- 若 \(l=r\)，则最多执行 \(2\) 次操作。
- 若 \(l\neq r\)，则：
- 第一步，让区间 \([l,r]\) 全部归零。操作最多执行 \(2\) 次。
- 第三、四步，让区间 \([l,r]\) 和区间 \([l,r-1]\) 分别整体做 \(\text{mex}\) 操作，操作最多执行 \(2\) 次。
- 现在考虑对区间 \([l,r]\) 的长度 \(r-l+1\) 从小到大讨论。
- 若 \(r-l+1=1\) 即 \(l=r\) 最多执行 \(2\) 次操作。
- 若 \(r-l+1=2\) 则归 \(0\) 最多 \(2\) 步，此时两次递归处理的时候归 \(0\) 操作最多执行 \(4\) 次，因此最多执行 \(6\) 次操作。
- 若 \(r-l+1=3\) 则同理，最多执行 \(2+4+8=14\) 次操作。
- 以此类推。因而当 \(r-l+1=k\) 即区间 \([l,r]\) 的长度为 \(k\) 的时候，最多执行的操作数量是 \(2^{k+1}-2\) 次。
- 因为 \(n=18\)，所以单次区间执行 \(\text{mex}\) 覆盖的次数最多为 \(2^{19}-2=524286>500000\) 次。但是容易发现这个方法很难使得 \(\text{mex}\) 覆盖操作执行的次数卡的这么满，所以是可以在 \(500000\) 次操作内得到答案的。
现在考虑证明多个区间的最多操作次数一定不会多于单个最大区间覆盖的区间的最多操作次数。
考虑将区间 \([l,r]\) 恰好拆分成 \([l,k]\) 和 \([k+1,r]\)。那么 \([l,r]\) 最多需要执行 \(2^{r-l+1}\) 次操作，\([l,k]\) 和 \([k+1,r]\) 分别最多需要执行 \(2^{k-l+1}\) 和 \(2^{r-k}\) 次操作，合并就是 \(2^{k-l+1}+2^{r-k}\) 次操作。容易证明 \(2^{r-l+1}\ge 2^{k-l+1}+2^{r-k}\)。
又因为若将 \([l,k]\) 区间缩水为 \([l,k-1]\) 区间，那么 \([l,k-1]\) 区间最多执行 \(2^{k-l}\) 次操作，有 \(2^{k-l+1}>2^{k-l}\)。缩水为 \([l+1,k]\) 区间也同理。
因此就证明了上述命题。因此这样的构造方案不会超出构造次数的限制。
考虑转化原问题。因此原问题的求操作后数列的最大和问题就变为了：
给定长度为 \(n\) 的序列 \(a\)。现在可以执行若干次操作，每一次操作可以选定一段区间 \([l,r]\) 并将这段区间内所有的元素全部赋值为 \(r-l+1\)。问最后 \(a\) 序列的最大和为多少。
这是一个很简单的 dp 问题。但是发现 \(n\le 18\) 所以直接按照上面的简单方法钦定每一个位置是否选择即可。记得要将两个部分分离计算，否则时间复杂度为优秀的 \(O(4^n\times n^2)\)。
若分离计算，则总的时间复杂度为 \(O(2^n\times n)\)。
代码实现：
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 18;
int a[N], b[N];
void mex(int l, int r) {
bool box[20] = {false};
for (int i = l; i <= r; i++)
if (a[i] <= 18)
box[a[i]] = true;
int val = 0;
while (box[val])
val++;
for (int i = l; i <= r; i++)
a[i] = val;
}
void clear(vector<pair<int, int>> &oper, int l, int r) {
if (accumulate(a + l, a + r + 1, 0ll) == 0)
return;
if (count(a + l, a + r + 1, 0ll) == 0) {
mex(l, r);
oper.push_back({l, r});
} else {
mex(l, r);
oper.push_back({l, r});
mex(l, r);
oper.push_back({l, r});
}
}
void fun(vector<pair<int, int>> &oper, int l, int r) {
if (l == r) {
clear(oper, l, r);
a[l] = 1;
return;
}
clear(oper, l, r);
fun(oper, l + 1, r);
mex(l, r);
oper.push_back({l, r});
mex(l, r - 1);
oper.push_back({l, r - 1});
fun(oper, l, r - 1);
}
signed main() {
int n;
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i];
int mx = accumulate(a, a + n, 0ll), id = 0;
for (int i = 1; i < (1ll << n); i++) {
for (int j = 0; j < n; j++)
b[j] = a[j];
vector<pair<int, int>> seg;
int l = -1, r = -1;
for (int j = 0; j < n; j++)
if (i >> j & 1) {
if (r == -1)
l = r = j;
else
r = j;
} else {
if (r != -1)
seg.push_back({l, r});
l = r = -1;
}
if (r != -1)
seg.push_back({l, r});
for (auto &[l, r] : seg)
for (int j = l; j <= r; j++)
b[j] = r - l + 1;
int now = accumulate(b, b + n, 0ll);
if (now > mx) {
mx = now;
id = i;
}
}
cout << mx << ' ';
if (!id) {
cout << "0 ";
} else {
vector<pair<int, int>> seg, oper;
int l = -1, r = -1;
for (int j = 0; j < n; j++)
if (id >> j & 1) {
if (r == -1)
l = r = j;
else
r = j;
} else {
if (r != -1)
seg.push_back({l, r});
l = r = -1;
}
if (r != -1)
seg.push_back({l, r});
for (auto &[l, r] : seg) {
fun(oper, l, r);
oper.push_back({l, r});
}
cout << oper.size() << '\n';
for (auto &[l, r] : oper)
cout << l + 1 << ' ' << r + 1 << '\n';
}
return 0;
}