Day 1

A

行列分别处理，随便枚举一下哪个坐标转完之后最小即可。

一种构造方案是：将 1 看成 (，0 看成 )，然后跑一个循环的括号匹配，把匹配上的右括号传过去。

第二遍把 1 看成 )，0 看成 ( 做一个对称的操作即可。

杜老师告诉我，这个模型是一个 Hypercube，然后做 Hypercube 的 symmetric decomposition，找到输入集合的补集在链上的对称点即可。

考虑分的两个子序列，它们值域有交的第一个位置，容易发现之后一定可以取到理论上界，也就是答案为：该位置前的答案 $+$ 满足所有元素小于子序列 $1$ 的 $\min$ 的最长下降子序列长度 $+$ 满足所有元素大于子序列 $2$ 的 $\max$ 的最长上升子序列长度。

在这个位置之前，两部分值域不交，一定只有 $O(n)$ 种情况，用线段树维护转移，每次将一个状态分裂成两个状态。对于最长上升子序列和最长下降子序列，倒着用线段树做一遍这个过程，把修改看做一些区间加，然后正着做的时候倒过来模拟这些区间加即可。

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

把集合放到 Trie 上考虑 mex-极限。不妨设当前子树中有数不存在于集合中，分类讨论：

左儿子没有满：mex-极限和左儿子的 mex-极限相等；
左儿子满了，右儿子中最小的数 $2^k$ 存在：mex-极限和右儿子的 mex-极限相等；
左儿子满了，右儿子中最小的数 $2^k$ 不存在，最大的数 $2^{k+1}-1$ 不存在：mex-极限是 $2^k$；
左儿子满了，右儿子中最小的数 $2^k$ 不存在，最大的数 $2^{k+1}-1$ 存在：此时一次操作后会将整个子树翻转，且翻转后的左子树不满，所以 mex-极限和右子树翻转之后的 mex-极限相等。

于是容易写出 DP 状态，使用 NTT 转移。

时间复杂度 $O(2^k k^2)$。

没咋看，看上去就是简单题。

跑一遍 DP，保留所有起点 DP 值为奇数或偶数（选择个数较多那个奇偶性）的区间，注意在最优方案中的区间需要保留，不能让答案小于 $\frac{m}{2}$。正确性显然。

将答案转化为 $n(n-1)m$ 减去每个人到达终点之后其他人走到检查点的次数求和。注意到检查点坐标的和不大，所以可以将其按照前缀长度 $\max$ 分成若干段，每一段贡献其实相同。

然后随便做一下，复杂度 $O(n\sqrt x)$。

给一个点点权增加 $1$，答案最多增加 $1$。于是可以从全 $l_i$ 慢慢增加到全 $r_i$。每个点增加的过程中一定是一段前缀对答案没影响，剩下来的后缀每次给答案 $+1$。用全局平衡二叉树做修改点权，查询全局最大独立集，然后容易找出这个前缀和后缀的分界点。

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