#P9579. 今我来思

    ID: 6195 传统题 1000ms 512MiB 尝试: 1 已通过: 1 难度: 7 上传者: 标签>CF2200提高排列构造极端元素优先处理交换论证懒标记线段树

今我来思

题目描述

小 G 手里有一个 00 到 n−1n − 1 的排列 pp,她不肯告诉小 W 具体内容,但允许小 W 多次询问某段区间的最小值。你偷听到了 qq 个询问,想还原出这个排列。

如果有多个符合询问结果的排列,可输出任意一个。如果小 G 在欺骗小 W(即不存在这样的排列),需要输出 nn 个 −1−1。

输入格式

第一行,两个正整数 nn 和 qq。

接下来 qq 行,每行三个整数 l,r,xl, r, x,表示区间 [l,r][l, r] 中 pp 值最小为 xx。

输出格式

一行,nn 个整数,表示答案,你需要保证每个数都在 [0,n−1][0, n − 1] 内。

样例

样例 1

5 3
0 2 1
1 3 0
1 4 0
1 4 3 0 2

样例 2

3 2
0 1 1
1 2 1
-1 -1 -1

数据范围

  • 子任务 11,分值 2323 分,保证 n,q≤10n, q \le 10。
  • 子任务 22,分值 4444 分,保证 n,q≤103n,q\le 10^3。
  • 子任务 33,分值 3333 分,保证 n,q≤105n,q\le 10^5。

注意:如果你无法判断最终答案是否为 −1-1,并且输出的是一个符合条件的数列,但不是 00 到 n−1n − 1 的排列,可以获得该子任务 30%30\% 的分数。例如在样例 22 中,输出 1 1 1 可获得这一部分分。