← 返回题目列表

AtCoder · utpc2024_l

L. LIS 三角形

中文机器翻译题面 查看原题

配点 : 100 点

問題文

正整数 N,K,L 提供。满足以下所有条件的长度 N 整数序列 给出 P 是否存在,并且如果存在的话, 1 请注明之一。

  • P 是整数列 (K, K + 1, \dots, K + N - 1) 的排列 给出了
  • P 的最长递增子序列的长度作为 L
  • 1 \leq i \leq N - 2 小于 i ,P_i, P_{i+1}, P_{i+2} 该值应乘以 3 边的长度(非退化)三角形存在。

T 测试用例,因此请逐一回答。

最长递增子序列是指 数列 P 可以得到第部分列是什么? 是P 的一些元素按原顺序排列而成的序列。 数列 P 可以得到第最長増加部分列是什么? 是P 的严格单调递增子序列,且长度为最大者。
非退化三角形是指 非退化三角形是,3 个顶点不在同一直线上排列的三角形。

制約

  • 所有输入均为整数
  • 1 \leq T \leq 50000
  • 3 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq 2 \times 10^5
  • 1 \leq L \leq N
  • 1 对于一个输入中包含的测试用例,N 的总和是 2 \times 10^5 以下

入力

输入是按以下格式从标准输入给出的。

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

每个案例均按以下格式给出。 打印

N K L

出力

按顺序输出每个测试用例的答案,以换行符分隔。

对于某个测试用例,输出满足所有条件的 P 不存在,则 No 。如果存在的话,请以以下格式输出满足所有条件的整数列 P 出 1 个,满足所有条件的整数列。 P 如果存在多个,其中任何一个输出都是正确的。 对于第

Yes
P_1 P_2 \dots P_N

入力例 1

3
6 3 4
5 5 5
7 1 2

出力例 1

Yes
3 6 4 7 5 8
Yes
5 6 7 8 9
No

1 个测试用例,满足条件的整数列中有 1 个, 有P=(3, 6, 4, 7, 5, 8) 。还存在其他满足条件的整数列。

2 关于第二个测试用例,P=(5, 6, 7, 8, 9) 是唯一满足条件的整数列。 对于第

3 个测试用例,满足条件的整数列 P 不存在。