T1

8 数码问题简化版， $O(7!)$ 爆搜 BFS，没了。

T2

\sum\limits_{i=0}^{m+1}\binom{n+1}{i}=\sum\limits_{i=0}^{m}\binom{n}{i}+\binom{n-1}{i}

\sum\limits_{i=0}^{m+1}\binom{n}{i}=\sum\limits_{i=0}^m \binom{n}{i}+\binom{n}{m+1}

时间复杂度为 $O(n)$ ，瓶颈在预处理组合数。

暴力枚举排列，逆序对也可以暴力统计，时间复杂度 $O(7!)$ 。

注意到暴力枚举排列不行，但是注意到这个只和排列奇偶性有关。本质上就是求行列式。具体的就是照题目的把矩阵 $[l_{i},r_{i}]$ 设为 1，其他设为 0。求行列式即可，时间复杂度 $O(n^3)$ 。

特判了所以没分。

首先我们到了 $O(n\log n)$ ，连暴力 $O(n^2)$ 初始化矩阵都无法初始化了就很难受。考虑到本题就是让你求行列式，那么目标就是优化求行列式的这一步骤。

我们考虑发掘一个性质，发现最大的性质就是行列式的取值就是 $\{ 0,1\}$ ，且 $1$ 是连续的一段。

考虑行列式展开：

\det M = \sum_{p} \operatorname{sgn}(p) \prod_{i=1}^n A_{i,p_{i}}

这个 $sgn$ 就是题目中的逆序对奇偶性，即 $(-1)^{\text{逆序对对数}}$ ，而 $p_{i}$ 就是我们枚举的排列。

根据过往在提高组线性代数课上，我把这个玩意叫做二分图完美匹配问题。

那么转化一下到二分图，一个合法排列相当于区间匹配问题：对于 $A_{i,p_{i}}$ ，每行选取的列是一个区间，要在区间里挑一个点，要求所有选取的列互不相同。

二分图建模相当于就是左部点是行 $i$ ，右部点是列 $j$ ，对于 $j\in [l_{i},r_{i}],i\to j$ 连边，问题转化为求二分图完美匹配和这个逆序对奇偶性。

这里我们顺序扫描列，枚举右部点来和左部点进行匹配。我们发现一个性质：

那么我们有一个贪心的想法，每次我们选择连边区间右端点最小的匹配。证明考虑反证法，如果不选右端点最小的区间，那么它很可能在后面用不了，导致全局无解释。

然后我们就可以做了，具体的，我们需要维护一个可并堆的结构，初始把所有区间插入每个左端点对应的堆里面，每次取出右端点最小的右端点，让后将剩下的元素放到 $heap_{i+1}$ 这个堆里面。

如果你不会可并堆，可以使用 Fhq-Treap 维护最小值和合并进行操作，但是我用可并堆是因为我一开始写 Fhq-Treap 写了一小时炸杠了 QAQ。

而奇偶性可以把高斯消元的代码抄过来，也是可以的，就是如果当前主元不再对角线上，我们可以把它交换回来，同时一次交换代表出现一个逆序对，将 ans 制反即可。

时间复杂度 $O(n\log n)$ 。

总结：图论模型的转化是一个比较常见的，对于优化如果无从下手是否可以考虑贪心的想法来进行优化？

好题

首先大量对优先级区间的查询操作，很容易想到使用线段树来维护优先级的查询，但是查什么？如何维护？

考虑发掘性质，发现一个关键性质就是结点数 $\le 9$ ，这是一个关键提示，而且题目中求的是多源最短路，联想 Floyd。

但是题目中还有一个限制就是走的优先级边必须单调不降，如果直接用 Floyd 做的话很难受不好处理性质。但是结点数很少，我们能不能……把每一个优先级对应的边用单独的图存下来？

思考这种方法可行性，注意到 Floyd 的本质其实是邻接矩阵的 $(\min,+)$ 广义矩阵乘法。也就是说这个又结合律，也可以上线段树维护！从左向右乘，正好满足了不同优先级道路之间的先后顺序。

做法也就这么出来了，注意到 $p$ 总共就 2000 个，所以创建最多 2000 个叶子节点，让后并对每个叶子结点跑一遍 Floyd 预处理出只走该优先级道路时的最短路。让后用线段树维护矩阵乘法。

查询的时候通过和线段树无任何差别，答案通过矩阵乘法统计即可。

反思：

当看到某个数据量极小的时候，我们要从它入手，分析性质，例如本题的结点数，上场模拟赛 T4 的 $k\le 5$ 。

应用线段树要灵活。一般进行区间修改，查询等操作的题目都可以使用线段树解决。其结点类型也不一定是“数”，只要是具有可并性的数据类型都可以当成结点，只要再对其各种操作进行相应修改即可。感觉要再复习一遍线段树理论了。