CF576D Flights for Regular Customers

考虑从小到大加入边，一个众所周知的结论是邻接矩阵的 $k$ 次幂就相当于走 $k$ 次后的路径条数。在这里我们只关心 $k$ 步后能否走到一个点，于是是 $01$ 矩阵。每加入一条边就进行一次矩阵快速幂，然后加入下一条边。

考虑如何计算答案。当且仅当加入一条边后在 $n$ 步内能走到终点，才说明可以走到终点，每加入一条边后判一下能否 $n$ 步内走到终点即可。

CF1187D Subarray Sorting

大概有两个做法，一个比较稳，也就是官方做法。从左到右考虑还原 $b$ 数组，直接判断一下下一个这个值的位置能否交换过来。这里的交换是两两交换，所以不会改变中间的东西的顺序，只要中间的东西都小于这个值即可。大概拿线段树维护一下就好了。

然后是杰哥想的做法，大概是对于每个位置考虑还原后它会到哪里（显然可以看成一个稳定排序，也就是没有交叉），然后对每个数看看是否会有左边的比它小的数移动到右边即可，然后发现就是个前缀最大值。其实这两种做法本质上来说差不多。

CF1399F Yet Another Segments Subset

我们可以把线段之间的包含关系建个图，发现必然是个 $\text{DAG}$ ，然后拓扑排序。考虑设 $dp[u]$ 表示选择 $u$ 这个区间以及一些它的子区间最多能选多少个。转移的时候枚举子区间，设 $f[i]$ 表示右端点最靠右的区间是 $i$ 的时候最多可以选择多少个区间。这个东西随便拿个 BIT 维护个前缀最小值即可。

复杂度 $O(n^2\log n)$。

CF1400E Clear the Multiset

考虑分治。不难发现对于一个区间如果都有值，我们进行 $1$ 操作的时候必然会让最小值变成 $0$ ，然后得到几个子问题。或者说，我们也可以直接对这个区间所有数用 $2$ 操作。分治解决即可。分治时每层复杂度都最坏 $O(n)$ ，复杂度是 $O(n^2)$。

CF1375E Inversion SwapSort

神仙题。这种题往往需要解决一个问题后转化到一个子问题（然后这也是我这辈子想不到的）。

我们考虑把 $n$ 移动到最后一个位置，把所有一端为 $n$ 的操作全部用掉，同时保持前面的数字的相对顺序不变。

具体做法是，把 $(pos[a_n+1],n),(pos[a_n+2],n),\dots,(pos[n],n)$ 依次操作一遍，于是可以发现这些位置相当于是分别减少了 $1$ ，同时归位了 $n$ ，并且用掉了所有关于 $n$ 的逆序对！

然后得到了一个子问题，继续做即可。