把每种颜色的首末出现位置看成区间，用栈扫描检查区间是否只存在包含关系；最大栈深就是最少轮数。
OJ: luogu
题目 ID: P3668
难度:提高+/省选-
标签:单调栈区间扫描线思维构造判定
日期: 2026-06-20 23:35
题意
给一个长度为 N 的最终颜色序列，0 表示空白。
原作者画画时，每种颜色只会刷一次，而且一次刷的是一个连续区间。
复制者要分若干轮来完成复制：
- 每轮可以刷若干个互不相交区间
- 每种颜色整个过程中也只能刷一次
要求最少需要多少轮；如果根本画不出来，输出 -1。
思路
先看一个更直观的慢版：
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 205;
int n;
int a[MAXN];
int first_pos[MAXN], last_pos[MAXN];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 0; i <= n; i++) {
first_pos[i] = 0;
last_pos[i] = 0;
}
for (int i = 1; i <= n; i++) {
cin >> a[i];
if (a[i] == 0) {
continue;
}
if (first_pos[a[i]] == 0) {
first_pos[a[i]] = i;
}
last_pos[a[i]] = i;
}
// 先检查是否存在交叉区间。
for (int x = 1; x <= n; x++) {
if (first_pos[x] == 0) {
continue;
}
for (int y = x + 1; y <= n; y++) {
if (first_pos[y] == 0) {
continue;
}
bool cross1 = first_pos[x] < first_pos[y] && first_pos[y] < last_pos[x] && last_pos[x] < last_pos[y];
bool cross2 = first_pos[y] < first_pos[x] && first_pos[x] < last_pos[y] && last_pos[y] < last_pos[x];
if (cross1 || cross2) {
cout << -1 << '\n';
return 0;
}
}
}
int ans = 0;
// 慢版枚举每个位置，显式找“覆盖这个位置的最内层区间”。
for (int i = 1; i <= n; i++) {
int cover = 0;
int top_color = 0;
int best_first = -1;
for (int color = 1; color <= n; color++) {
if (first_pos[color] == 0) {
continue;
}
if (first_pos[color] <= i && i <= last_pos[color]) {
cover++;
if (first_pos[color] > best_first) {
best_first = first_pos[color];
top_color = color;
}
}
}
if (a[i] == 0) {
if (cover != 0) {
cout << -1 << '\n';
return 0;
}
continue;
}
if (top_color != a[i]) {
cout << -1 << '\n';
return 0;
}
ans = max(ans, cover);
}
cout << ans << '\n';
return 0;
}brute.cpp 直接按定义检查：
- 任意两种颜色区间是否交叉
- 每个位置真正露在最上层的颜色是不是当前颜色
- 最大覆盖层数是多少
这个版本适合帮助理解题意，但正式解可以做到线性。
核心观察是：
对每种颜色，只看它在最终画面中的：
- 第一次出现位置
- 最后一次出现位置
就能把它看成一个区间。
合法画面中的这些颜色区间只能：
- 互不相交
- 或者一个完全包含另一个
如果出现：
text
l1 < l2 < r1 < r2这样的交叉关系，就说明某种颜色会被切成两段，而它又只能刷一次连续区间，所以必定无解。
于是可以从左到右扫描整个序列，并用栈维护“当前已经开始但还没结束”的颜色区间。
扫描到位置 i 时：
- 如果是某颜色第一次出现，就把它入栈
- 当前颜色必须等于栈顶颜色，否则无解
- 如果是某颜色最后一次出现，就把它出栈
还要特别注意 0：
- 如果当前位置是
0，但栈还不空 - 说明某个颜色区间内部出现了空白
- 这同样无解
栈深度的最大值，就是同一时刻叠在一起的颜色层数，也就是复制者最少需要的轮数。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int n;
int a[MAXN];
int first_pos[MAXN], last_pos[MAXN];
int stk[MAXN], top_idx;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) {
first_pos[i] = 0;
last_pos[i] = 0;
}
for (int i = 1; i <= n; i++) {
cin >> a[i];
if (a[i] == 0) {
continue;
}
if (first_pos[a[i]] == 0) {
first_pos[a[i]] = i;
}
last_pos[a[i]] = i;
}
top_idx = 0;
int ans = 0;
for (int i = 1; i <= n; i++) {
if (a[i] == 0) {
if (top_idx > 0) {
cout << -1 << '\n';
return 0;
}
continue;
}
if (i == first_pos[a[i]]) {
stk[++top_idx] = a[i];
ans = max(ans, top_idx);
}
if (stk[top_idx] != a[i]) {
cout << -1 << '\n';
return 0;
}
if (i == last_pos[a[i]]) {
top_idx--;
}
}
cout << ans << '\n';
return 0;
}复杂度
每种颜色最多入栈一次、出栈一次，整段扫描只做线性处理。
所以时间复杂度是：
空间复杂度是：
总结
这题的关键不是去想“每轮怎么刷”，而是先看最终颜色区间之间必须满足什么结构。
一旦看出：
- 合法区间只能包含或分离，不能交叉
- 扫描时最上层颜色就是当前打开区间里的最内层颜色
就能自然得到栈解法。
一图流解析
这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。
