A7461 · 舞台拼色

题目描述

在一场大型文艺汇演中，共有来自不同地区的代表队参与表演。每个代表队的成员穿着统一颜色的服装，用编号表示其颜色。 导演希望通过一系列调度操作，让舞台上的演员最终呈现出一幅理想的颜色排列效果。 共有 $n$ 个代表队，每个代表队有足够多的成员，且第 $i$ 个代表队的服装颜色编号为 $i$。 舞台上有一排位置，共 $m$ 个，从左到右编号为 $1$ 到 $m$。开始时舞台上没有演员。 导演将进行若干次操作，每次操作选择一个**尚未使用过的代表队**，并指定一个区间 $[L, R]$。该代表队的成员会占据舞台上从第 $L$ 到第 $R$ 的所有位置： - 如果某个位置上已经有演员，则原演员会被替换； - 新上场的演员全部来自同一个代表队，因此这些位置的颜色会被统一为该代表队的编号。 每个代表队**最多只能被使用一次**。 现在给定导演希望最终舞台上从左到右的颜色序列 $a_1, a_2, \dots, a_m$。 你的任务是：构造一组操作，使得经过这些操作后，舞台上的颜色排列**恰好等于目标序列**。 如果无法实现，输出 $-1$。

- 第一行包含两个整数 $m, n$，表示舞台位置数量和代表队数量。 - 第二行包含 $m$ 个整数 $a_1, a_2, \dots, a_m$（$1 \le a_i \le n$），表示目标颜色序列。

- 第一行输出一个整数 $k$。 - 若无解，输出 $-1$； - 否则，$k$ 表示需要进行的操作次数。 - 若 $k \neq -1$，接下来输出 $k$ 行，每行三个整数 $c_i, L_i, R_i$： - 表示第 $i$ 次操作选择编号为 $c_i$ 的代表队， - 并让其成员占据区间 $[L_i, R_i]$。 - 所有 $c_i$ 必须互不相同。 如果存在多种可行方案，输出任意一种即可。

输入 #1

7 10
10 5 5 10 4 2 4

输出 #1

输入 #2

5 2
1 2 1 2 1

输出 #2

-1

输入 #3

6 5
1 1 4 5 1 4

输出 #3

-1