chx记录一种新颖的排列构造方法。
我们先看一个相对而言更弱的问题，如果初始的时候整个网格是空的，那么有多少摆放方法呢？这个题我们首先需要从蛇的长度限制上获得一个非平凡的观察：摆放的方法远比我们预期的要少
我们作如下的实验：摆蛇先摆长的，之后再摆短的。于是不难观察到，如果对于格点 $(x,y)$ 而言它的权值 $v_{x,y}:=x+y$ 那么第一条蛇的起点和终点的权值一定是 $2,2n$ ，而第二条蛇的起点和终点一定是 $3,2n-1$ ，之后是 $(4,2n-2),(5,2n-3),...,(n+1,n+1)$ 。这是对第一个观察
- 长度为 $x$ 的蛇的起点和终点的权值一定分别是 $n+2-x,n+x$ .
之后在这个观察的基础上我们发现一条蛇的路径上的点的权值是关于 $n+1$ 对称的，那当我们放入一条蛇的时候其实就是把棋盘的某一个部分分成两个部分，既然我希望蛇能够完全填充完全部格子，那么割开的这两个部分的每个部分的格点的权值的分布应该也是关于值 $n+1$ 对称的，之后可以用归纳法来证明：为了达到这个目标，所有蛇的形状都是关于斜线 $(x,n+2-x):x\in[1,n]$ 对称的。这是第二个观察
- 所有蛇的形状都是关于斜线 $(x,n+2-x):x\in[1,n]$ 对称的.
根据这两个观察我们已经足够能够回答这个更弱的问题了。在一个合法的摆放方案中我们可以把每条蛇的长度都记录蛇的中间（就是那条斜线上），于是我们得到了一个长度为 $n$ 的排列，于是我们把所有合法的摆放方法都射入了长度为 $n$ 的排列中。
接下来我们来说明这个映射的单射性和满射性，主要就是构造出对应。考虑左下角的蛇，假定它的长度是 $x$ ，那么要怎么摆呢？肯定是尽量贴着左下角摆，不能空出空穴，之后的蛇也要这么摆，不然缺出来的空位后面的蛇是无法填补的。于是固定了排列后填法就是唯一的了，所以空方格的填法就是 $n!$ .
那么我们会看到这个题目，题目除了长度还给定了蛇的形状，事实上蛇能够直走就可以理解为蛇当前这个数在先前的位置没出现过，而蛇要拐弯就意味着这个数在先前的位置已经出现过了。于是我们就构造出了一系列限制：
求有多少个排列满足：第 i 个数在区间 li,ri 之间出现，并且这个区间是特殊的：要么包含要么不交，于是可以建立一个树形结构直接进行计数就可以了。