第一次自己独立做出来的*2500，纪念一下
首先模拟样例不难发现我们可以确定在\(l,r\)中出现过的数字（称这些数为“固定数”）的相对顺序（比如第一个样例，相对顺序为6 4 2 5，我们只用插入\(1\)和\(3\)就好了），用链表维护就好了
考虑剩下的某个数\(x\)，不难发现它能放在的地方必须要求与其相邻的固定数至少有一个比其大，所以随着\(x\)的减小，其能够放的位置越来越多（而且之前能放的现在也一定能放），不难启发我们想到“水の数列”这道题目。对于\(x\)，我们统计其在固定数中有多少个可以放的位置（比如样例一，对于\(3\)来说就可以放在\(6,4,5\)三个数字的旁边，一共有\(5\)个位置可以放），设为\(kg\)，在算上之前已经放置了的不是固定数的数（每多放置一种这个数可以放的位置就多\(1\)），设为\(sum\)，那么当前数字可以放的位置就是\(kg+sum\)，对每一个\(x\)都这么考虑最后利用乘法原理乘起来就好了；由于我们不需要像“水の数列”这道题目一样知道连通区间的长度，所以我们用变量简单判断就好了，具体来说，比如当前循环到的数为\(x\)，我们正在考虑将其放在固定数\(y,z\)之间（注意\(y,z\)在固定数数列中是相邻的），那么如果\(y,z\)都比\(x\)大，\(kg\)没有变化，如果\(y,z\)都比\(x\)小，\(kg\)增加二，如果只有一个大于\(x\)，那么\(kg\)增加一
标签：位置,kg,数列,Splittable,数为,Permutations,样例,固定 From： https://www.cnblogs.com/dingxingdi/p/18335279