汉堡杯题解。

· · 个人记录

T1

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

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

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

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

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

T2

经典的转 01 trick。

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

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

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

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

T3

我们考察 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

T4

尝试扫描线，对于一个 $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$ 后面新增的所有前缀最小值，并且同步的更新区间的权值即可。