C++ 入门之递归算法。

这个让一批批人上场的过程很像染色。一种颜色的刷子只能用一次。

考虑如何完成 $[l, r]$ 的合法染色。

• 如果 $a_l = a_r$。先对整个区间染色成 $a_l$。然后递归处理。令 $p_0,p_1,\dots,p_k$ 为 $[l, r]$ 内颜色 $a_l$ 的出现位置。则递归处理 $[p_0+1,p_1-1],[p_1+1,p_2-1],\dots[p_{k-1}+1,p_k-1]$。
• 否则，令 $a_l$ 下一次出现的位置为 $p$，则递归处理 $[l+1,p-1]$ 和 $[p+1,r-1]$。

考虑怎样判断无解。当我们想给区间 $[l, r]$ 染色 $c$ 时，如果区间外还存在这种颜色，即无解。

#include <bits/stdc++.h>

using namespace std;

const int N = 3e5 + 10;

int n, m, a[N], cnt;
vector<int> vec[N];

struct Node {
	int l, r, w;
}p[N];

vector<int> res;
int mn[N], mx[N];

bool solve(int l, int r) {
	if (l > r) return true;

	if (p[l].w == p[r].w) {
		res.push_back(p[l].w);
		if (vec[p[l].w][0] < l || vec[p[l].w].back() > r) return false;
		for (int i = 0; i + 1 < vec[p[l].w].size(); ++ i ) {
			if (!solve(vec[p[l].w][i] + 1, vec[p[l].w][i + 1] - 1)) return false;
		}
	} else {
		if (!solve(l, vec[p[l].w].back())) return false;
		if (!solve(vec[p[l].w].back() + 1, r)) return false;
	}
	
	return true;
}

int st[N][20];

int query(int l, int r) {
	int k = log2(r - l + 1);
	return max(st[l][k], st[r - (1 << k) + 1][k]);
}

void solve() {
	cin >> n >> m;
	
	memset(mn, 0x3f, sizeof mn);
	memset(mx, -0x3f, sizeof mx);
	for (int i = 1; i <= n; ++ i ) {
		cin >> a[i];
		if (a[i] == a[i - 1]) {
			p[cnt].r ++ ;
		} else {
			p[ ++ cnt] = {i, i, a[i]};
		}
		mx[a[i]] = max(mx[a[i]], i);
		mn[a[i]] = min(mn[a[i]], i);
	}
	
	for (int i = 1; i <= cnt; ++ i ) {
		vec[p[i].w].push_back(i);
	}
	
	if (!solve(1, cnt)) {
		cout << -1;
		return;
	}
	
	cout << res.size() << '\n';
	for (int v : res) cout << v << ' ' << mn[v] << ' ' << mx[v] << '\n';
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int T = 1;
#ifdef tests
	cin >> T;
#endif
	while (T -- ) solve();
	return 0;
}