相当于我们让每一行/每一列去和所有点进行匹配，要求所有点都匹配上，每一行每一列只能用一次。

考虑图论建模，原图上一个点 $(x,y)$ 视作 $x$ 行和 $y$ 列连了一条边，建出来一个图。

这个图上一条边 $x - y$ 的含义是，尝试让点和边做匹配，定义和上面的类似，要么让 $x$ 点与这条边匹配，要么让 $y$ 点与这条边匹配，不能不匹配。

所以容易发现，如果一个点数为 $k$ 的连通块，有 $>k$ 条边，答案一定是 $0$。

否则容易发现，如果一个连通块形态是树有 $k$ 种选法，否则有 $2$ 种选法，不同连通块之间独立，乘起来就行。

经典的转 01 trick。

观察我们需要维护的两个排列，发现我们只要能知道这样的一个信息就能算答案：

对于每个点 $i$，满足 $p_j<p_i$ 的所有点 $j$，因为我把题忘了所以我其实不太记得我需要什么了。

于是考虑 $dp$，设 $dp_S$ 表示我目前已经确定 $1$ 到 $|S|$ 这些数的位置，它们恰好被填在了 $S$ 位置集合里（注意我们并不关心哪个数究竟在哪，只关心这些数所在的位置集合）。

每次新加入一个值 $|S|+1$，枚举其所在的位置，然后就能算出逆序对的增加量并转移。

我们考察 $b_1,b_2,...,b_k$ 在数组内连续出现，可以改写成：满足 $b_2$ 在 $b_1$ 后面一个，$b_3$ 在 $b_2$ 后面一个，...，$b_k$ 在 $b_{k-1}$ 后面一个这些条件同时成立。

维护所有这样的 $(b_i,b_{i+1})$ 二元组，尝试找到所有能让这两个数相邻的时刻，如果能维护出来每个二元组中两个数相邻的时刻的集合，求答案相当于求若干个集合的交。

每次修改是单点修改，只会影响 $O(1)$ 个二元组的状态（相邻变为不相邻，或不相邻变为相邻），而操作是随机的，每个二元组出现的时刻，能用 $O(\frac{m}{n^2})$ 个区间表示，因为看上去选择每一个二元组的概率均等，每个二元组期望状态改变 $O(\frac{m}{n^2})$ 次，维护这些出现时刻的区间是容易的。

集合求交可能需要写个分治合并，从前往后合并复杂度有可能是假的，所以这个算法复杂度大概是 $O(\frac{mq}{n^2}+？)$。

然后我们倒闭了，因为 $n$ 可能很小。

但是注意到我们改成维护 $(b_i,b_{i+1},b_{i+2})$ 同时出现的时刻，区间个数就对了，此时可能是 $O(\frac{mq}{n^3}+?)$ 的复杂度。

很厉害！！！11

$dp_i$ 表示已经选完了 $[1,i]$ 的贡献最大值。

尝试扫描线，对于一个 $r$ 维护每个左端点 $l$ 对应的区间 $[l,r]$ 的贡献，每次将 $r$ 增加 $1$，并整体维护每一个左端点对应区间的贡献。

换句话说，线段树维护若干个节点，第 $l$ 个节点上维护的是 $dp_{l-1}+cost(l,r)$ 的值。

$\max,\min$ 权值是容易算的，用单调栈可以变成 $O(n)$ 次区间加。

$mex$ 看上去有些难，改写一下定义，维护一个 $lst_i$ 表示值 $i$ 在 $[1,r]$ 中最后一次出现是在哪个位置，此时 $mex(l,r) = \min_{lst_i<l}i$，也就是最小的满足 $lst_i<l$ 的 $i$。

那么容易发现，我们只关心 $lst_i$ 的前缀最小值，设其下标分别为 $p_1<p_2<...<p_k$，那么 $(lst_{p_{i+1}},lst_{p_i}]$ 这一段左端点的 $mex$ 就是 $p_{i+1}$。

每次右端点移动一位，相当于令目前 $lst_{a_r} = r$，由于右端点是递增的，此时 $r$ 一定是 $lst$ 数组内最大值，考虑修改完前缀最小值如何变化。

如果 $lst_{a_r}$ 不是前缀最小值，没任何影响。

否则 $lst_{a_r}$ 将被移出前缀最小值，此时暴力的找 $lst_{a_r}$ 后面新增的前缀最小值的复杂度是对的，因为一个点在成为前缀最小值后，只有 $lst_{a_r} = r$ 的操作可以让一个点从前缀最小值变为非前缀最小值，因此总新增的前缀最小值是 $O(n)$ 级别的。

我们只需要线段树二分找到 $a_r$ 后面新增的所有前缀最小值，并且同步的更新区间的权值即可。