题解

难点不在于把所有颜色都印上去，而在于某种颜色只能用一次：它被覆盖以后，就没有机会补回来了．我们先弄清每种颜色必须印在哪里，再考虑哪些操作能放进同一轮．

先确定每种颜色的区间

记颜色 $c$ 第一次、最后一次出现的位置为 $L_c,R_c$．只考虑目标中出现过的颜色．

颜色 $c$ 的一次印制必须同时印到这两个位置，所以至少要覆盖整个 $[L_c,R_c]$．印得更长会不会有帮助？不会．在一个最终正确的方案中，如果它还印了这个区间外的某个位置，该位置最后不是颜色 $c$，一定会被后面的操作覆盖．把这部分删去，不会影响最终结果，也不会增加同一轮中区间相交的情况．

因此，我们可以固定颜色 $c$ 只印 $[L_c,R_c]$．现在要做的是给这些固定区间安排轮次．

颜色很少时，枚举印制顺序

子任务 1 至多只有六种颜色，可以枚举出现过的颜色的全部顺序．按这个顺序染色，检查最后是否得到目标彩带．

对于一个检查通过的顺序，再计算它至少需要几轮．如果前面某个颜色的区间与当前区间相交，当前颜色必须在它之后印制；与当前区间不相交的颜色不影响当前轮次．所以当前轮次就是所有这些相交的前驱轮次的最大值加一，没有前驱时为一．

这样压缩轮次不会改变相交操作的先后关系，也就不会改变最终颜色．反过来，任何合法分轮方案都可以把各轮依次展开成一个枚举到的顺序．在所有检查通过的顺序中取最小轮数，就得到答案．

设实际出现 $k$ 种颜色，时间复杂度为 $O(m+k!(kn+k^2))$，空间复杂度为 $O(n+m)$．该做法可以通过子任务 1，得到 15 分．

先把“谁必须先印”写出来

考虑颜色 $c$ 的区间 $[L_c,R_c]$．如果其中某格最终要求颜色 $d\ne c$，颜色 $d$ 就必须在颜色 $c$ 之后印制，否则这格最后会被 $c$ 覆盖．记一条有向边 $c\to d$．

把每种颜色的整个区间扫描一遍，就能得到全部依赖．

• 如果依赖有环，就不可能安排出合法顺序，答案为 $-1$．
• 如果没有环，按照拓扑顺序计算每种颜色最早能在哪一轮印制．没有前驱的颜色在第一轮；其他颜色的轮次为所有前驱的最大轮次加一．答案是最大的轮次．

还需要确认：没有依赖的两个区间，真的能放到同一轮吗？两个区间只要相交，就至少有一个区间的端点落在另一个区间里．这个端点最终要印成自己所属的颜色，因此至少产生一条依赖．所以同一轮中的区间确实不会相交．

按这个轮次印制时，对于任意位置 $i$，所有覆盖它、但不是颜色 $a_i$ 的操作，都必须排在 $a_i$ 前面．这就保证了最终结果正确．而依赖链上的每种颜色必须占用不同轮，拓扑计算的轮数也不能再减少．

设 $H=\sum_c(R_c-L_c+1)$．扫描建边和拓扑处理的时间为 $O(n+m+H)$．最坏情况下 $H=O(n^2)$，可以通过子任务 2．子任务 3 中每个颜色的区间最多有 $31$ 格，$H\le31n$，同一做法也能通过．

边不一定要全部存下来：第一次扫描区间时统计入度，拓扑队列取出颜色 $c$ 时，再扫描一次 $[L_c,R_c]$，更新其中其他颜色的入度和轮次．同一对颜色间的重复边，只要前后两次都按相同次数处理，就不会影响结果．这样空间只要 $O(n+m)$．

这个做法可以通过子任务 1、2、3，共 60 分．

不把依赖逐条列出来

继续看两个颜色的首末区间．

如果它们相交却互不包含，例如 $L_c<L_d<R_c<R_d$，那么 $L_d$ 要求 $d$ 后印，$R_c$ 又要求 $c$ 后印，产生矛盾．所以合法的两个区间只能不相交，或者一层套一层．

如果颜色 $d$ 的区间在颜色 $c$ 的区间里面，那么 $d$ 必须后印．还要注意，里面不能再出现一个最终要求颜色 $c$ 的位置，否则 $d$ 会覆盖它，颜色 $c$ 又不能再用一次．样例 2 正是这种情况．因此，只检查区间有没有交叉还不够．

从左往右扫，用栈保存已经开始、但还没结束的颜色：

1. 到达颜色 $c$ 的第一次出现位置时，将它入栈．
2. 这一格最终要求的颜色必须等于栈顶，否则无解．
3. 到达颜色 $c$ 的最后一次出现位置时，将它出栈．

为什么第二步必须成立？栈中的区间都覆盖当前格子，内层颜色必须比外层颜色后印．最后留下的就只能是最内层，也就是栈顶颜色．如果新开始的区间跨过了旧区间的右端点，那么扫到旧区间的右端点时，旧颜色同样不会在栈顶，也会被发现．

若整个扫描没有失败，按照每种颜色入栈时的深度安排印制轮次：第一层在第一轮，第二层在第二轮，以此类推．同一深度的区间互不相交；在每个位置，最后印上去的是最深的一层，恰好是扫描检查过的目标颜色．所以这个方案一定可行．

同时，任意一条嵌套链中的颜色必须逐层后印，需要的轮数至少是链长．最大栈深既是下界，又能通过上述方案达到，因此就是答案．

每个位置检查一次，每种颜色至多入栈、出栈一次．加上数组初始化，总时间复杂度为 $O(n+m)$，空间复杂度为 $O(n+m)$．这个做法可以通过所有子任务．

参考代码

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> a(n + 1), first(m + 1, 0), last(m + 1, 0);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (!first[a[i]]) first[a[i]] = i;
        last[a[i]] = i;
    }
    vector<int> st;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        int c = a[i];
        if (first[c] == i) {
            st.push_back(c);
            ans = max(ans, static_cast<int>(st.size()));
        }
        // 尚未结束的最内层颜色，必须就是这一格最终需要的颜色．
        if (st.empty() || st.back() != c) {
            cout << -1 << '\n';
            return 0;
        }
        if (last[c] == i) st.pop_back();
    }
    cout << ans << '\n';
    return 0;
}