88 lines
1.5 KiB
Markdown
88 lines
1.5 KiB
Markdown
|
# 还原排列
|
|||
|
|
|
|||
|
|
## 题目描述
|
|||
|
|
|
|||
|
|
Alice有一个 $0\sim n$ 的排列 $p$，她告诉你 $m$ 条信息，每条信息形如 $(l,r,val)$，表示区间 $[l,r]$ 的 ${\rm mex}$ 值为 $val$。
|
|||
|
|
- 一个区间的 ${\rm mex}$ 值是最小的没有在这个区间中出现的自然数。
|
|||
|
|
|
|||
|
|
你想要猜出Alice的排列 $p$，或声明无解。
|
|||
|
|
|
|||
|
|
## 输入格式
|
|||
|
|
|
|||
|
|
第一行两个整数 $n$ 和 $m$。
|
|||
|
|
|
|||
|
|
随后 $m$ 行每行三个整数 $l,r,val$ 描述一条信息，表示区间 $[l,r]$ 的 ${\rm mex}$ 值为 $val$。
|
|||
|
|
|
|||
|
|
## 输出格式
|
|||
|
|
|
|||
|
|
如果不存在满足所有条件的排列，输出 $-1$。
|
|||
|
|
|
|||
|
|
否则输出一行 $n+1$ 个正整数，表示一个 $0$ 到 $n$ 的排列。
|
|||
|
|
|
|||
|
|
**本题采用 Special Judge**。如果满足条件的排列有多个，你可以输出任意一个。
|
|||
|
|
|
|||
|
|
## 样例 #1
|
|||
|
|
|
|||
|
|
### 样例输入 #1
|
|||
|
|
|
|||
|
|
```
|
|||
|
|
3 4
|
|||
|
|
0 0 0
|
|||
|
|
0 1 1
|
|||
|
|
0 2 2
|
|||
|
|
1 3 3
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
### 样例输出 #1
|
|||
|
|
|
|||
|
|
```
|
|||
|
|
3 0 1 2
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
## 样例 #2
|
|||
|
|
|
|||
|
|
### 样例输入 #2
|
|||
|
|
|
|||
|
|
```
|
|||
|
|
5 7
|
|||
|
|
0 1 0
|
|||
|
|
4 5 0
|
|||
|
|
1 3 1
|
|||
|
|
0 5 6
|
|||
|
|
0 5 6
|
|||
|
|
2 5 3
|
|||
|
|
2 3 1
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
### 样例输出 #2
|
|||
|
|
|
|||
|
|
```
|
|||
|
|
4 3 5 0 1 2
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
## 样例 #3
|
|||
|
|
|
|||
|
|
### 样例输入 #3
|
|||
|
|
|
|||
|
|
```
|
|||
|
|
见下发样例
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
### 样例输出 #3
|
|||
|
|
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
## 提示
|
|||
|
|
|
|||
|
|
对于所有的数据满足：$1 \le n,m\le 5\times 10^5$，$ 0\le l,r\le n$，$0\le val\le n+1$。
|
|||
|
|
|
|||
|
|
- Subtask 1(15 points)：$n,m\le 10$；
|
|||
|
|
- Subtask 2(20 points)：$n,m\le 20$；
|
|||
|
|
- Subtask 3(10 points)：$val=0$；
|
|||
|
|
- Subtask 4(15 points)：排列和区间边界都随机生成；
|
|||
|
|
- Subtask 5(10 points)：$n\le 10^5$；
|
|||
|
|
- Subtask 6(30 points)：无特殊限制。
|
|||
|
|
|
|||
|
|
请注意使用效率较高的 IO 方式。
|