赛后 4min 切，有点可惜。不过能让我学到知识的题就是好题。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意解析：
定义一个排列的逆序值为所有满足 1≤l<r≤n1\le l\lt r\le n1≤l<r≤n 且区间 [l,r][l,r][l,r] 存在至少一个逆序对的 l,rl,rl,r 的数量。
给定两个正整数 n,kn,kn,k，请你构造一个长度为 nnn 的排列，使得该排列的逆序值为 kkk。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
看似是构造题，实则不然。
首先考虑如何求一个排列的逆序值。
我们可以分别计算 [1,i][1,i][1,i] 对于逆序值的贡献，然后加起来。
例如 A=[1,3,2,6,4,5]A=[1,3,2,6,4,5]A=[1,3,2,6,4,5]。
* i=1i=1i=1：区间就一个元素，显然没有贡献逆序值。
* i=2i=2i=2：显然也没有贡献逆序值。
* i=3i=3i=3：注意到 (A2,A3)(A_2,A_3)(A2 ,A3 ) 构成了一对逆序对，所以贡献出 l=1,r=3l=1,r=3l=1,r=3，l=2,r=3l=2,r=3l=2,r=3，共 222 组。
* i=4i=4i=4：还是 (A2,A3)(A_2,A_3)(A2 ,A3 ) 构成逆序对，贡献出 l=1,r=4l=1,r=4l=1,r=4，l=2,r=4l=2,r=4l=2,r=4，共 222 组。
* i=5i=5i=5：(A4,A5)(A_4,A_5)(A4 ,A5 ) 构成逆序对，贡献出 l=1,r=5l=1,r=5l=1,r=5，l=2,r=5l=2,r=5l=2,r=5，l=3,r=5l=3,r=5l=3,r=5，l=4,r=5l=4,r=5l=4,r=5，共 444 组。
* i=6i=6i=6：贡献出 l=1,r=6l=1,r=6l=1,r=6，l=2,r=6l=2,r=6l=2,r=6，l=3,r=6l=3,r=6l=3,r=6，l=4,r=6l=4,r=6l=4,r=6，共 444 组。
注意到，如果 Ai>Ai−1A_i\gt A_{i-1}Ai >Ai−1 ，则 [1,i][1,i][1,i] 对逆序值的贡献与 [1,i−1][1,i-1][1,i−1] 对逆序值的贡献相同；如果 Ai<Ai−1A_i\lt A_{i-1}Ai <Ai−1 ，则 [1,i][1,i][1,i] 对逆序值的贡献为 iii。这个结论不难证明。
那这个对正解有什么帮助吗？
我们可以考虑 DP，求出一种合法的方案，使得区间对逆序值的贡献符合上面的规则。
dp[i][j][k]dp[i][j][k]dp[i][j][k] 记录是否存在第 iii 个数，[1,i][1,i][1,i] 对逆序值的贡献为 jjj，总逆序值为 kkk 的情况，如果存在，则 [1,i−1][1,i-1][1,i−1] 对逆序值的贡献可能是多少。
然后进行 dfs，枚举这种情况的每一个 AiA_iAi 是否满足 Ai>Ai−1A_i\gt A_{i-1}Ai >Ai−1 。
接下来就是构造环节了。首先令 Ai=iA_i=iAi =i，然后对于连续的需要满足 Ai>Ai−1A_i\gt A_{i-1}Ai >Ai−1 的数，对这一块进行翻转即可。对，构造部分就是这么简单。
代码：
时间复杂度：O(n3+tn)O(n^3+tn)O(n3+tn)。
