Vasya And Array

题意翻译

## 题目描述 ```Vasya```有一个数组$a[1...n]$ 你从来没听说过这个数组，但```Vasya```会告诉你 $m$ 条关于这个数组的信息。每条信息包含三个参数$t_i,l_i,r_i(0\leq t_i \leq 1 ,1 \leq l_i < r_i \leq n)$，其含义分别为： - 如果 $t_i=1$ 则说明子数组$a[l_i...r_i]$ 是一个不降序列 - 如果 $t_i=0$ 则说明子数组$a[l_i...r_i]$ 不是一个不降序列。一个数组 $a$ **不是一个不降序列**说明存在两个相邻元素$a[i] ,a[i+1]$使得$a[i]>a[i+1]$ 举个栗子：假设$a=[2,1,1,3,2]$ ，然后 ```Vasya``` 告诉你： $t_1=1,l_1=2,r_1=4$，意思是 $a[2...4]=[1,1,3]$是一个不降序列 $t_1=0,l_1=4,r_1=5$，意思是 $a[4...5]=[3,2]$不是一个不降序列 $t_1=0,l_1=3,r_1=5$，意思是 $a[4...5]=[1,3,2]$不是一个不降序列 然而就算```Vasya``` 告诉你这么多条件，你依然不会知道数组 $a$，但是请你找出一种可能的情况。 ## 输入输出格式 ### 输入格式 第一行有两个整数$n,m(2\leq n\leq 1000 ,1 \leq m \leq 1000)$ 接下来 $m$ 行每一行有三个整数 $t_i,l_i,r_i$表示一条信息，含义见题目描述 ### 输出格式 如果```Vasya```自相矛盾，只需输出```NO``` 如果有解，请先输出```YES```，之后输出 $n$ 个整数 $a_1,a_2...,a_n(1\leq a_i \leq 10^9)$。有多组解请任意输出一种。

题目描述

Vasya has an array $ a_1, a_2, \dots, a_n $ . You don't know this array, but he told you $ m $ facts about this array. The $ i $ -th fact is a triple of numbers $ t_i $ , $ l_i $ and $ r_i $ ( $ 0 \le t_i \le 1, 1 \le l_i < r_i \le n $ ) and it means: - if $ t_i=1 $ then subbarray $ a_{l_i}, a_{l_i + 1}, \dots, a_{r_i} $ is sorted in non-decreasing order; - if $ t_i=0 $ then subbarray $ a_{l_i}, a_{l_i + 1}, \dots, a_{r_i} $ is not sorted in non-decreasing order. A subarray is not sorted if there is at least one pair of consecutive elements in this subarray such that the former is greater than the latter. For example if $ a = [2, 1, 1, 3, 2] $ then he could give you three facts: $ t_1=1, l_1=2, r_1=4 $ (the subarray $ [a_2, a_3, a_4] = [1, 1, 3] $ is sorted), $ t_2=0, l_2=4, r_2=5 $ (the subarray $ [a_4, a_5] = [3, 2] $ is not sorted), and $ t_3=0, l_3=3, r_3=5 $ (the subarray $ [a_3, a_5] = [1, 3, 2] $ is not sorted). You don't know the array $ a $ . Find any array which satisfies all the given facts.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ m $ ( $ 2 \le n \le 1000, 1 \le m \le 1000 $ ). Each of the next $ m $ lines contains three integers $ t_i $ , $ l_i $ and $ r_i $ ( $ 0 \le t_i \le 1, 1 \le l_i < r_i \le n $ ). If $ t_i = 1 $ then subbarray $ a_{l_i}, a_{l_i + 1}, \dots , a_{r_i} $ is sorted. Otherwise (if $ t_i = 0 $ ) subbarray $ a_{l_i}, a_{l_i + 1}, \dots , a_{r_i} $ is not sorted.

输出格式

If there is no array that satisfies these facts in only line print NO (in any letter case). If there is a solution, print YES (in any letter case). In second line print $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 10^9 $ ) — the array $ a $ , satisfying all the given facts. If there are multiple satisfying arrays you can print any of them.

输入输出样例

输入样例 #1

7 4
1 1 3
1 2 5
0 5 6
1 6 7

输出样例 #1

YES
1 2 2 3 5 4 4

输入样例 #2

4 2
1 1 4
0 2 3

输出样例 #2

NO

题意翻译

## 题目描述 ```Vasya```有一个数组$a[1...n]$ 你从来没听说过这个数组，但```Vasya```会告诉你 $m$ 条关于这个数组的信息。每条信息包含三个参数$t_i,l_i,r_i(0\leq t_i \leq 1 ,1 \leq l_i < r_i \leq n)$，其含义分别为： - 如果 $t_i=1$ 则说明子数组$a[l_i...r_i]$ 是一个不降序列 - 如果 $t_i=0$ 则说明子数组$a[l_i...r_i]$ 不是一个不降序列。一个数组 $a$ **不是一个不降序列**说明存在两个相邻元素$a[i] ,a[i+1]$使得$a[i]>a[i+1]$ 举个栗子：假设$a=[2,1,1,3,2]$ ，然后 ```Vasya``` 告诉你： $t_1=1,l_1=2,r_1=4$，意思是 $a[2...4]=[1,1,3]$是一个不降序列 $t_1=0,l_1=4,r_1=5$，意思是 $a[4...5]=[3,2]$不是一个不降序列 $t_1=0,l_1=3,r_1=5$，意思是 $a[4...5]=[1,3,2]$不是一个不降序列 然而就算```Vasya``` 告诉你这么多条件，你依然不会知道数组 $a$，但是请你找出一种可能的情况。 ## 输入输出格式 ### 输入格式 第一行有两个整数$n,m(2\leq n\leq 1000 ,1 \leq m \leq 1000)$ 接下来 $m$ 行每一行有三个整数 $t_i,l_i,r_i$表示一条信息，含义见题目描述 ### 输出格式 如果```Vasya```自相矛盾，只需输出```NO``` 如果有解，请先输出```YES```，之后输出 $n$ 个整数 $a_1,a_2...,a_n(1\leq a_i \leq 10^9)$。有多组解请任意输出一种。