Codeforces Round 939 D. Nene and the Mex Operator 【构造、思维、状压】

D. Nene and the Mex Operator

题意

给定一个长度为 $n$ 的正整数数组 $a$，定义操作：

• 选定一个区间 $[l,r]$，将区间内的数字替换成：$mex(a_l,a_{l+1},...,a_r)$

要求在不超过 $5\cdot 10^5$ 次操作下， 最大化数组的和

思路

首先需要注意到一个很关键的点：对于一个长度为 $len$ 的区间 $[l,r]$，不管怎样对这个区间操作，最终这个区间的每个数最大就是 $len$，排除掉 $a_i$ 本身就比 $len$ 大的情况
这是因为如果要产生 $mex=len$，那么就需要 $0,1,...,len-1$ 共 $len$ 个数，再大的 $mex$ 值区间长度就不够放了

因此我们可以大胆猜测（对构造题很重要）：一个长度为 $len$ 的区间可以构造出 $len$ 个 $a_i=len$，也就是最后一次操作是 $[l,r]$，且 $mex=len$

如何操作？我们将区间移动到前缀 $[1,len]$，就是对应代码 $solve(k,p)$ 函数，$k=len$，$p=l$，表示将前 $k$ 个数变为全 $k$ 需要的操作

注意在每次进入 $solve$ 之前，我们需要保证区间全零
具体原理就是：$a_k=0$ 不动，先递归求解 $solve(k-1)$，现在 $[1,k-1]$ 全为 $k-1$
然后我们将 $[1,k-2]$ 设置为全零，再递归求解 $solve(k-2)$，保持 $a_{k-1}=k-1$ 不变
一直循环下去，直到前缀为：$1,2,3,....,k-1,0$，这时 $mex$ 就等于 $k$ 了

这样子递归操作的次数大约为 $O(2^n)$
这是因为：$solve(k)$ 要调用一次 $solve(k-1)$，而后调用 $solve(k-2)\to solve(1)$，
而 $solve(k-1)$ 也会调用 $solve(k-2)\to solve(1)$，因此 $solve(k)$ 大于是 $solve(k-1)$ 调用次数的 $2$ 倍，也就是说，这是一个公比大约为 $2$ 的等比数列

得出这个结论和构造方式后，我们就可以采用状压二进制枚举操作的区间，其余保留原值即可

// Problem: D. Nene and the Mex Operator
// Contest: Codeforces - Codeforces Round 939 (Div. 2)
// URL: https://codeforces.com/contest/1956/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define fore(i,l,r)	for(int i=(int)(l);i<(int)(r);++i)
#define fi first
#define se second
#define endl '\n' 
#define ull unsigned long long

const int INF=0x3f3f3f3f;
const long long INFLL=0x3f3f3f3f3f3f3f3fLL;

typedef long long ll;

std::vector<std::pair<int, int>> opt;

void solve(int k, int p){
	if(k == 1){
		opt.push_back({p, p});
		return;
	}
	solve(k - 1, p);
	for(int i = k - 2; i > 0; --i){
		opt.push_back({p, p + i - 1}); //turn [1, i] to 0
		solve(i, p);
	}
	opt.push_back({p, p + k - 1});
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    fore(i, 0, n)	std::cin >> a[i];
    int ans = 0;
    int sta = 0;
    fore(S, 0, 1 << n){
    	std::vector<bool> v(n);
    	fore(j, 0, n)	v[j] = (S >> j & 1);
    	int sum = 0;
    	int len = 0;
    	fore(i, 0, n){
    		if(!v[i]){
    			sum += len * len;
    			len = 0;
    			sum += a[i];
    		}
    		else ++len;
    	}
    	sum += len * len;
    	if(sum > ans){
    		ans = sum;
    		sta = S;
    	}
    }
    std::vector<std::pair<int, int>> vec;
	int i = 0;
	int l = -1;
	while(i < n){
		if(!(sta >> i & 1)){
			if(l != -1)	vec.push_back({l + 1, i});
			l = -1;
		}
		else if(l == -1) l = i;
		++i;
	}
	if(l != -1)	vec.push_back({l + 1, n});
	
	for(auto [l, r] : vec){
		fore(p, l, r + 1)
			if(a[p - 1])
				opt.push_back({p, p}); //turn a[p] to 0
		solve(r - l + 1, l);
	}
	
    std::cout << ans << ' ' << opt.size() << endl;
    for(auto [l, r] : opt)	std::cout << l << ' ' << r << endl;
	return 0; 
}