新年的平衡兔环

idea, data, std, solution from 127

算法 1

对于前两个子任务，容易发现 puts("Yes") 即可。

期望通过子任务 $1$、$2$，得到 $40$ 分。

算法 2

容易发现，条件即能够形成一个多边形，因此充要条件为$R\cdot (\sum a_i-\max a_i)\geqslant r\cdot \max a_i$。

期望得到 $100$ 分。

新年的搜索记录

idea, data, std, solution from ix35.

算法 1

每次 $O(|S|\log |S|)$ 求最大后缀并接到后面。

期望通过子任务 $1,2$，得分 $40$ 分。

算法 2

我会猜答案！

打个表发现，每次加的最大后缀长度要么是等差数列，要么是等比数列（每次翻倍）。

所以只要求出前三项，就可以简单推出后面部分的情况了。

期望通过所有子任务，得到 $100$ 分。

算法 3

我会 Border 理论！

设 $T=g(S)$，则 $f(S)=ST$，考虑 $g(ST)$ 会是什么样子的。由于 $T$ 是 $ST$ 的后缀，所以肯定 $g(ST)\ge T$，同时由于 $T=g(S)$，所以 $g(ST)$ 肯定形如 $RT$，其中 $R$ 既是 $T$ 的一个后缀（因为 $R$ 是 $S$ 的后缀，又不可能比 $T$ 长，否则肯定 $RT < T$），又是 $T$ 的一个前缀（否则比较 $T$ 和 $RT$ 中的 $R$ 部分就可以知道 $RT < T$），所以是 $T$ 的一个 Border。

设 $R_0$ 是 $T$ 的最短 Border，通过比较 $RT$ 和 $R_0T$ 可以归纳证明 $R=R_0^l$（每次剥掉一个 $R_0$），显然 $l$ 越大越好，所以这里 $R$ 就应该取最短 Border 的最大整数次重复。

有了上面的结论，容易证明，如果 $R=T$，那么 $f^k(S)$ 的最大后缀为 $T^{2^k}$；如果 $R\ne T$，那么 $f^k(S)$ 的最大后缀为 $R^kT$，于是模拟 $k$ 次操作后的结果就很简单了。

期望通过所有子任务，得到 $100$ 分。

算法 4

我会 Lyndon 理论！

考虑将字典序反转，将 $S$ Lyndon 分解（按照反转后的字典序），设为 $S=w_1^{p_1}w_2^{p_2}\ldots w_k^{p_k}$，可以证明原来的最大后缀一定形如 $s_i=w_i^{p_i}\ldots w_k^{p_k}$，并且 $s_{i+1}$ 是 $s_i$ 的前缀，但 $s_i$ 不是 $s_{i-1}$ 的前缀。可以用 Duval 算法求出这个 $s_i$，它就是 Duval 算法第一次遍历完 $S$ 的最后一个字符时的后缀。

设 $S$ 的最大后缀为 $A=s_i$，再设 $B=w_k^{p_k}$，那么 $f(S)=SA$。现在考虑 $SA$ 的 Lyndon 分解应该是怎样的，模拟 Duval 算法可以发现最前面的 $w_1^{p_1}\ldots w_{k-1}^{p_{k-1}}$ 应该是不变的（这跟 $S$ 后面的部分根本没关系），但是到了 $w_k^{p_k}(=B)$ 就不一样了，注意 $C=Bw_i^{p_i}w_{i+1}^{p_{i+1}}\ldots w_{k-1}^{p_{k-1}}$ 是一个 Lyndon 串，并且 $A'=CB$ 是一个近似 Lyndon 串（因为 $B$ 是 $C$ 的前缀），所以最后部分的 Lyndon 分解应该是一个 $C$ 和一个 $B$。

因此新串 $f(S)=SA$ 的最大后缀是 $BA$，而 Lyndon 分解的最后一段则不变，仍是 $B$（如果 $B=A$ 则是 $B^2$ 了）。

所以 $f^k(S)$ 的最大后缀就是 $B^kA$，当然 $B=A$ 需要特判，此时为 $A^{2^k}$，我们得到了和正解 2 相同的结论。

如果利用 Lyndon 分解求最大后缀，可以做到 $O(|S|)$ 复杂度，当然用后缀数据结构或哈希来替代也可以通过本题。

期望通过所有子任务，得到 $100$ 分。

新年的双区间操作

idea, data from qingyu; solution, std from huahua, std2 from csy2005

算法一

题目太难了，写个暴力跑路吧。

我们每次暴力进行所有操作，时间复杂度为 $O(nmq)$，可以通过子任务 $1$，得到 $5$ 分。

算法二

我们注意到所有操作都形如求一个区间的最大值，或者将整个区间与某个值取 max，这是可以直接通过线段树解决的。

因此我们使用线段树优化算法一中的暴力，通过子任务 $1$ 与子任务 $2$，得到 $15$ 分。

算法三

一个重要的想法是，一个操作执行多次和执行一次的效果是一样的，因此目的是不漏的找到所有被触发了的操作，而无需关系是否找重复的问题。

一个操作$i$可以被触发，要么是因为 $\max_{k=l_i}^{r_i} a_k \ge x_i$，要么是因为存在一个操作 $j < i$，满足操作$j$被触发了并且$[l'_j,r'_j] \cap [l_i, r_i] \not= \varnothing, y_j \ge x_i$。

我们分开考虑这两部分贡献。

考虑 $l = r = l' = r'$，每个位置独立。因此不需要考虑区间有交的限制。

注意到第二个部分的条件是形如 $j$ 能触发且 满足某些要求，那么$i$ 能触发的形式。那么可以很自然的定义出 $f_i$ 表示如果$i$能触发，那么包括$i$以及可以因此触发的操作$y$ 的 $\max$。

考虑如何转移 $f$。暴力转移为 $f_i = \max( \max_{i < j , y_i \ge x_j} f_j, y_i)$，相当于一个二维偏序，也就是按照$x_j$排序，$f_j$作为权值的一个前缀$\max$，需要动态修改，用树状数组维护即可。

考虑对 $a$ 修改等价于 $O(n+q)$ 次查询 $a_i$ 能在 $i$ 位置上触发哪些操作。也就是按照 $x_i$ 排序后的一个前缀，区别是没有修改，可以线性计算前缀 $\max$。

时间复杂度 $O(m\log n + n+q)$，期望得分 $10$ 分。结合暴力可以得到 $25$ 分。

算法四

每个位置之间不互相独立了，但是不太影响。我们仍然采用算法2中的 $f$ 转移。区别是我们不能对于每一个位置扫描他的操作，而是强制在线的同时处理 $n$ 个位置上总计 $m$ 个操作。数据结构部分需要离散化/动态开点线段树/平衡树等技巧解决。

时间复杂度 $O(m\log n + n+q)$，期望得分 $25$ 分。结合暴力可以得到 $40$ 分。

算法五

接下来需要正面面对区间有交的限制。一种方法是直接上树套树，这个做法非常好写，但是常数较大。

具体来说，我们对长度为 $n$ 的序列建立线段树。把每个操作看成一次查询和一次修改。对于线段树节点$[l, r]$维护两个 map，分别表示所有和$[l, r]$有交但不包含的修改的 $(x_i, f_i)$ 点对；表示包含 $[l, r]$ 但不包含其线段树上父亲节点的修改的所有 $(x_i, f_i)$ 点对。 具体来说，前者可以形象的理解为线段树维护子树信息，后者可以理解为需要标记永久化的懒标记。

修改在会在 map 上插入一个点对，查询则是要支持查询前缀 $\max$。这个可以很好的利用 stl 的 map 完成。注意到只有按照 $x$ 排序后 $f$ 是前缀最大值的位置有用，因此 map 里只保留前缀最大值的位置，查询 lowerbound 一下即可。

时间复杂度 $O((m + n + q) \log n \log m)$，期望得分 $60$ 分。

按照算法四的思路继续优化，可以做到 $O(m \log n \log m + (n + q) \log n)$，不过就失去了其好写的优势，因此不多赘述。

算法六

考虑直接对操作序列 cdq 分治，对权值扫描线。

具体来说， $[l, mid]$ 里的操作按照 $y_i$ 排序，$[mid + 1, r]$ 里的操作按照 $x_i$ 排序。对于每个左侧的操作能触发的对应右侧一个前缀与其有交的区间。仍然是触发多次不会影响思想，将其转化成对于每个位置，如果两个区间都包含了这个位置那么形成一次转移。因此右侧的每个操作可以看成对线段树区间 checkmax，左侧的操作相当于查询区间max，都可以很好的用线段树解决。

注意到后面 $O(n+q)$ 次查询，没有时间维度，可以不扔到 cdq 分治里，而是直接进行 cdq 分治内部的扫描线线段树。

时间复杂度 $O(m \log n \log m + (n + q) \log n)$。期望可以通过所有子任务，得到 $100$ 分。

新年的传火仪式

idea, data, std, solution from Melania

出题人谢罪

首先要承认，这题在比赛的时候没能提供足够的区分度，在此我深表歉意！

这题的数据范围分成了 $\text{A}$ 和 $\text{B}$ 两种类型，这样的出题方式我肯定是不欣赏的，我要自我检讨，大家以后也千万不要效仿我这么做！主要是一开始觉得两个做法各有特点就都想保留，可是我大大低估了实现难度和细节处理的复杂程度。

大家如果要补题的话，我建议只补数据类型 $\text{B}$ 的做法。我数据类型 $\text{A}$ 的设置，实在是背离了当今 $\text{OI}$ 健康的发展方向。

问题分析

我们首先对问题做一个重新表述。拿出 $[l,r]$ 中的所有 > 操作，依次编号为 $1,2,\cdots,t$。设火炬所处位置为 $i$，枚举 $j$，若第 $j$ 个 > 操作进行时 $i$ 在座则令 $i$ 加 $1$，否则 $i$ 不变。初始时 $i=1$，要求 $j$ 扫完 $t$ 时 $i$ 的值。

设一共有 $\text{width}$ 个 > 操作，令 $a(i,j)\in\{0,1\}$ 表示 $i$ 在第 $j$ 个 > 操作进行时在不在座。考虑一个 $n$ 行 $\text{width}$ 列的表格，其中 $(i,j)$ 可能是黑格或白格，对应 $a(i,j)=1/0$。

想象一枚棋子初始时放在第 $1$ 行，若当前处于黑格就向右下走 $1$ 步，否则就向右走 $1$ 步。设 $c_i$ 表示第 $i$ 个操作后首个 > 操作，则棋子初始在 $(1,c_l)$，向右向下不断游走，我们要求出首次游走到第 $c_{r+1}$ 列时所处的行。

称上述这个结构为「黑白表格」，接下来我们的讨论均在黑白表格上进行。注意到黑白表格是要随着 $l$ 发生变化的。

算法一

从 $1\sim n$ 枚举表格的行，维护 $q$ 枚棋子首次到达该行时所在的列。那么每枚棋子都要寻找该行内的下一个黑格。

$l$ 从 $m$ 到 $1$ 扫描线，每遇到一个该行的 1 操作就将 $[c_{该操作},c_{下一个同行的0/1操作})$ 内的格子都变成黑格。这样一来，我们只需要对颜色已经确定的一个后缀从后往前递推出下一个黑格的位置即可。预先将询问按 $l$ 排序与该行的操作归并以保证在正确的时间处理询问。

实现的时候为了方便起见，我们认为表格有 $n+1$ 行和 $\text{width}+1$ 列，其中最后一行一列均永远全为白格。

时间复杂度 $\mathcal{O}\big(n(m+q)\big)$，应能通过子任务 $1$ 得到 $10$ 分。

算法二

注意到随着 $l$ 减小，表格上的黑格有增无减。同时初始格子也单调变左。因此我们有单调性，具体地：随着 $l$ 的减小，棋子首次到达某行时所在的列单调向左变化。

枚举行，设 $\text{cur}(l)$ 表示从 $l$ 开始的询问首次到达该行时所在的列。我们用线段树维护 $\text{cur}(1)\sim\text{cur}(m)$ 的序列。‘

有两种修改：区间赋值、全局 $+1$。区间赋值是指寻找下一个黑格：下一个黑格一定是某个 1 操作的 $c$，必须有 $\text{cur}(l)\leq c$。另外下一个黑格还不能更早，设上一个 1 操作是 $i$，则要么 $l>i$ 要么 $\text{cur}(l)$ 在上一个 1 操作的影响范围的右侧。

由于对 $l$ 的限制和对 $\text{cur}(l)$ 的限制均构成一段区间，利用单调性可知它们的交也一定是一段区间。利用线段树二分找到这个区间，直接区间赋值即可。

现在考虑回答询问。对于询问 $[l,r]$，我们需要在 $\text{cur}(l)$ 首次 $\geq c_{r+1}$ 的行将其回答掉。我们预先将所有在 $l$ 的询问按 $r$ 排序，再用一棵线段树维护 $r$ 最小的那个询问的 $c_{r+1}$。如果只有区间赋值操作，我们可以不断取出该区间的最小值直到最小值都不能被回答为止，每次取出一个询问要更新 $l$ 处最小的 $c_{r+1}$。这样均摊复杂度是正确的，然而无法处理全局 $+1$ 操作。

我们可以直接忽视全局 $+1$ 操作的存在。到第 $i$ 行时一共加了 $i-1$，据此调整我们对线段树里 $\text{cur}$ 值的认知即可。我们希望只在区间赋值操作时回答询问，然而有的询问是在全局 $+1$ 操作时被回答的。我们只需要做一些微调：设询问 $[l,r]$ 在第 $i$ 行作为最小值被取出。考虑 $\text{cur}(l)$ 的实际值。若 $\leq c_{r+1}$ 则答案就是 $i$，否则答案 $=i-\big(\text{cur}(l)-c_{r+1}\big)$。

其实类似于坐标系变换，我们将第 $i$ 行整体向左推 $i-1$ 格，将原先的向右/向右下 $1$ 格变为向右/向下 $1$ 格，跨行时 $\text{cur}(l)$ 就无需改变。

时间复杂度 $\mathcal{O}\big((n+m)\log m+q\log q\big)$，应能通过子任务 $3$ 得到 $50$ 分。

算法三

初始在座情况的存在和 ! 操作的存在都破坏掉了单调性，这显著提高了问题的复杂程度。

我们考虑带权分块，令 $i$ 的权值 $=$ 针对 $i$ 的修改操作个数 $+1$。设定一个值 $B$，将 $[1,n]$ 划分为若干个权值和 $\leq B$ 的不交区间。当然可能有权值 $>B$ 的单个行，我们希望在 $\mathcal{O}(m+q)$ 内处理单个行，在 $\mathcal{O}(m+q+B^2)$ 内处理一个块。

首先是处理单个行，这部分做法和子任务 $1$ 类似。倒着归并操作和询问，每遇到一个该行的 ! 操作就将 $[c_{该操作},c_{下一个同行的0/1操作})$ 内的格子都黑白反转。遇到该行的与初始在座情况不同的 0/1 操作时也一样。

每个时刻该行的格子分为三个部分：尚未被反转过的部分，已经被反转过的部分和已经确定下来的部分。找下一个黑格时枚举三个部分看要找的黑格是否落在其内。对于第三部分，逆推出下一个黑格即可。对于第二部分，我们每做一个反转就在反转区间的左端点打 $1$ 个反转标记，维护反转标记的后缀和。逆推出下一个后缀和的奇偶性与当前不同的格子即可。

更重要的是如何处理整个块。一个块有两个任务：一是根据 $q$ 枚棋子首次到达块首行时所在的列推出它们首次到达下一块首行时所在的列；二是回答所有撑不到下一块的询问。两个任务都需要对棋子在该块内的运动情况进行刻画。

对于所有针对该块的操作 $i$ 在 $c_i$ 处设置一个关键点。从关键点出发会到达另一个关键点，我们连一条有向边。那么棋子会沿着关键点形成的内向森林行走。另外，从关键点出发还可能直接运动到某行的第 $\text{width}+1$ 列，或者直接走到下一块的首行。

$l$ 一定时黑白表格一定。我们做一个坐标系变换，将第 $i$ 行整体向左推 $i-1$ 格。相当于对一个格子，要求其下方第一个白格，并进一步求其右方第一个黑格。注意到我们的列被划分为了 $\leq B$ 个区间，每个区间内的列每行的黑白情况均相同。我们将一个区间缩成一个格子可以得到一张「浓缩表格」。我们即是要在浓缩表格的每行每列上做动态后继问题。

由于权值和 $\leq B$，我们的 $l$ 也被划分为了 $\leq B$ 个区间，每个区间内 $l$ 的表格在该块内相同。倒着枚举 $l$ 的等价类，维护浓缩表格。新增一个操作的影响是浓缩表格上的区间反转。我们用压缩 $\text{Trie}$ 来维护列的动态后继，每次修改暴力重构行的动态后继。这里由于序列长度 $\leq B$ 压缩 $\text{Trie}$ 只需要开两层。当然这很不优美，实际上我们有严格根号的做法。

将 $l$ 的等价类与询问做归并。对一个等价类我们用上面的做法预处理出关键点的后继。然后我们递推出从每个关键点开始走到达的最后一个关键点。对于一个询问我们也需要求一次后继得出其到达的首个关键点。利用这些信息，加以一些较为复杂的分类讨论，即可得出每枚棋子运动的轨迹。对于那些运动不到下一块的棋子，我们则需要暴力跳这棵树。

上文提到的严格根号的做法基于这样一个事实：我们会问动态后继的格子只有 $\mathcal{O}(B)$ 个。这些格子将每列切成一些连续段，我们只需要分别在这些连续段内做动态 $\text{mex}$ 问题即可。这可以离线用线性并查集做到线性。$\text{not practical}$。

时间复杂度 $\mathcal{O}\big((n+m)\sqrt{m+q})$，应能通过子任务 $5$ 得到 $50$ 分。结合算法二，可以获得 $100$ 分。

新年的找对

idea, data, std from 127

solution1 by 127

此即tech round:E

subtask1,2

暴力，状压，乱搞均可。

subtask3

一般图最大匹配是这个问题的特殊情形，因此如果写组合算法将如同带花树。

subtask4

最大流是这个问题的特殊情形，因此如果写组合算法也会类似网络流。

正解

Part I

即 matroid parity problem，又称matchoid，拟阵奇偶问题。

普通的matchoid问题是NPC的，但在此处我们需要考虑的是线性拟阵奇偶问题，已有多项式复杂度算法，此即拟阵可在域上线性表出。

拟阵奇偶问题的特化有拟阵交，网络流，一般图最大匹配等等，还有被称为$\Delta$拟阵的版本。

线性拟阵的问题可以简单表述：在一线性空间中取值，有$m$对向量，选出最多的对数$k$，使得选出的这$2k$个向量线性无关。

代数算法不同于组合算法，通常使用线性代数的工具进行分析和构造。

此问题中，有一种称为稀疏型构造的构造：

$$ \begin{bmatrix} - & A \\ A^T & T \end{bmatrix} $$

其中$A$为$[a_{1}^1,a_{1}^2,a_{2}^1,a_{2}^2...,a_{i}^1,a_{i}^2,...,a_{m}^1,a_{m}^2]$。

$T$为$A$的匹配矩阵：

$$ \mathrm{diag}\left\{\begin{bmatrix}0 & x_1 \\ -x_1& 0\end{bmatrix},\begin{bmatrix}0 & x_2 \\ -x_2& 0\end{bmatrix},...,\begin{bmatrix}0 & x_m \\ -x_m& 0\end{bmatrix}\right\} $$

其中$x_i$为线性空间基域上代数无关的未定元，可以理解为扩域下代数无关的元素。

记$\nu(A)$为元素对集$A$的答案，我们有：

$$ 2\nu(A)=\mathrm{rank}\left(\begin{bmatrix}- & A \\A^T & T\end{bmatrix}\right)-m $$

我们需要一个引理：

对于混合斜对称矩阵$K+T$，$K$为数值斜对称矩阵，$T$为代数斜对称矩阵，$K+T$非奇异当且仅当存在$K$的主子矩阵$K[S]$有$K[S]$和$T[U\backslash S]$均非奇异。

其中$K[S]$表示$K$行列集合均为$S$的主子矩阵，$U$为全集。

证明只需对斜对称矩阵展开Pfaffian即可。

然后我们考虑构造的正确性，设集合$S$所表示的主子矩阵线性无关，即$\mathrm{rank}=|S|$，显然此主子矩阵包含矩阵$T$，设此主子矩阵为$W$，则由引理，有子集$V$使得$W$被分解为$K+T$形式后$K[S\backslash V]$与$T[V]$均非奇异，由$K$的形式知$K$为对称矩阵，且有分块形式使左下右上均为方阵，方阵对应$S\backslash V$，且由$T$的形式知，$T[V]$为很多对的并，那么$S\backslash$也由很多对的并组成，故知$S\backslash V$构成一组合法方案，反之亦然。

稀疏型矩阵过于庞大，使用经典的打洞技巧，用$Schur$补的秩恒等式即可转化得到紧凑型：

$$ 2\nu (A)=\mathrm{rank} \sum_{i}x_i\cdot a_i^1 \wedge a_i^2 $$

其中$\wedge$为楔积$a\wedge b=ab^T-ba^T$

接下来所有的构造将在此基础上进行。

Part II

首先路径不符合构造的想法，即图拟阵，我们将路径松弛为树，那么考虑尽量大的边集构成生成树，每棵树不含超过两种颜色的点即可。

而我们容易从最多的边数推得答案，以及从边集的方案构造答案。

考虑生成树本身需要一个图拟阵，因而边拟阵的线性表出需要本身需要设计为$[x,-x]$的形式，而我们则需要设计另一个向量的形式以保证颜色数不超过$2$。

考虑到仍有不同色的限制，因此我们可以选取一些二维子空间来实现这一点。

取空间$(F^2)^n$，为每条边$e(u,v)$选取一二维子空间$L_e=\{(0,0,...,0,x_u,0,...,0,x_v,0,...)\}$，其中$x_u+x_v=0$，$x_u\in F^2$，基由两个向量组成。

我们还剩为数不多的方法引入点的限制，为每种颜色$c$的点选取$F^2$上的一维子空间$Q(c)$使其之间独立，对颜色$0$单独选取$Q(0)=0$，设其基为$q_c$。

令每个点$v$有$R(v)=(0,0,...,0,q_{c_v},0,...)$，令$Q$为所有$R(v)$的张成。

那么我们以商空间的形式引入点的限制：对于边的子集$S$，$L_S/(L_S \cap Q)$无关，即$L_S\cup Q$无关。

边的连接相当于一种传递的作用，手动消元可知同一棵树内既不存在相同颜色的两点，也不存在三种不同的颜色。

由于可假设除去连接相同颜色的边，我们可知$\dim{L_e/Q}=2$，但有可能某些边集的空间的张成可以交$Q$非平凡。

那么怎么可知$L_S\cup Q$独立?这看起来是一个经典的线性代数问题，即几个与$Q$独立的空间与$Q$合起来不独立。

我们的想法是提前让其他向量在$Q$中商干净，即先将空间分解为$Q$与$Q$的补的直和，那么独立当且仅当向量在$Q$的补中的部分独立。

如果有内积结构，取正交补则是容易的（内积空间，Schmit），如何取$Q(c)$，取$L_e$，如何取补之上的分解，读者可自行尝试，只须满足条件即可，笔者的标算和_rqy的题解中所提到的可以作为参考。

Part III

求出答案是容易的，若设答案为$r$，则我们可用经典手段做到$O(mr^3)$甚至$O(mr^2)$，注意到楔积在矩阵中的位置关系，以及答案的级别，我们再一次尝试使用打洞方法用分治优化复杂度。

关于这一点的实现细节，_rqy 的题解有更详细的论述。

Part IV

实现以及说说话，标算采用了动态矩阵优化空间复杂度，好像可以直接复用矩阵，然后在矩阵乘法，求逆处均有优化，特别是对于$AB^{-1}$的求解，将$B$的求逆过程复用在一起。

笔者出这个问题，一是为了压轴，二是为了宣传代数算法，最主要的目的还是让选手对于较为学术的研究有一个熟悉，这是OI避不开的问题，何时自己研究何时找寻背景，我想OI中独自研究的时间并不会多，大量的问题都是在重复甚至很多看起来不可解的问题其实都早已有了答案，这时就不可能以"毒瘤，论文"等方式避开这样的问题（浪费了时间，你会难过），而在了解更多内容之后，以OIer的水平，可以较为容易甚至轻易地做出自己的结果，这样一来，从两边都改善了学术界和普通竞赛之间的关系（OIer是很强的劳动力）。

Part V

还有很多matchoid的应用，我来列举一下，免得其他老哥（以及我）拿原题出：

Xuong tree，Pinning number，3-degree Feedback Vertex Set，3-hypergraph maximum spanning tree。

会作为模板题添加一些到uoj。

solution2 by _rqy

详见 https://uoj.ac/blog/8048 。