ROIR 2024
评分 \(\in[0,10]\)。
https://www.luogu.com.cn/problem/list?type=luogu&page=1&tag=479|61
登机 (Day 1)
\(2\)。
模拟。
如果在有一个有人的位置，它的对称位置没人，那就在对称位置放一个人。
如果有剩余，那么就去找若干对对称的空位放人即可。
双调序列 (Day 1)
\(3.5\)。
处理出 \(l_i,r_i\)，分别表示右端点为 \(i\) 的递增序列长度和左端点为 \(i\) 的递减序列长度，乘法乘起来就是这个 \(i\) 的贡献。
一定不会记重。
表格游戏 (Day 1)
\(4\)。
容易发现行列之间互相独立。
可以选择 \(O(2^h)\) 枚举行的状态，同时 \(O(2^{\frac{w}{2}})\) 对列进行折半搜索，可以做到 \(O(2^(h+\frac{w}{2}))\)，\(h+\frac{w}{2}\le 23\)，足以通过。
树根 (Day 1)
\(6\)。
注意数据范围 \(nk\le 2\times 10^5\)。
对于一个根，很难找到确定的策略最小化最大深度，考虑二分答案 \(mid\) 转为判定问题。
每次取出深度最深的节点 \(u\)，让根向 \(u\) 的 \(mid-1\) 级祖先连边（\(mid-1+u\)），重复 \(k\) 次，判断此时最深的节点的深度是否小于等于 \(mid\)。
上述过程可以用线段树维护。
现在要对每个点求其作为根时的答案，考虑换根，维护换根时的变化：深度，子树区间，\(k\) 级祖先。深度可以直接在线段树上区间修改，后两者分讨根和当前节点的关系就行。
这样的复杂度是 \(O(nk\log^2 n)\) 的，注意到相邻节点的答案差值不超过 \(1\)，无需二分，只需枚举判定 \(\le 1\) 的变化量，所以可以做到 \(O(nk\log n)\)。
数组划分 (Day 2)
\(3.5\)。
需要分到不在同一组的两个数，一定满足质因子个数相差 \(1\)，也就是奇偶性不同。
保证有解，直接按质因子个数奇偶性分类就行了。
细菌 (Day 2)
\(3\)。
意义不明。
细菌的数量具有单调性，直接二分答案。
三等分的数组 (Day 2)
\(4.5\)。
转到值域上 dp，状态记录当前数 \(i\) 剩几个，\(i-1\) 剩几个，钦定 \(i-2\) 已经一个不剩，进行两种转移：\(i\) 与自己配对，\(i-1,i,i+1\) 配对，转移需保证让 \(i-1\) 配对完全。
虽然状态数看着比较像 \(O(nm^2)\)，但是容易发现 \(\sum c_i=m\)，不难证明是 \(O(m^2)\) 的。
二叉树的遍历 (Day 2)
\(6.5\)。
想了很久 polylog 做法无果，点开题解一看是全是根号做法，心脏骤停。
首先要对于点 \(x,y\)，大分讨 \(y\) 比 \(x\) 先遍历的情况。
-
\(x\) 为中序遍历，\(y\) 在 \(x\) 的左子树。
-
\(x\) 为后序遍历，\(y\) 在 \(x\) 的子树。
-
存在一个 \(x,y\) 的公共祖先 \(z\)，\(y\) 在 \(z\) 左子树，\(x\) 在 \(z\) 的右子树。
这三种都可以预处理，因为第一、二种只关心 \(x\) 的操作状态，而第三种不关心点的操作状态。
-
\(y\) 为先序遍历，\(x\) 在 \(y\) 的子树中。
-
\(y\) 为中序遍历，\(x\) 在 \(y\) 的右子树中。
如果是单点修改，这两个也可以用树状数组简单做，但是这个是区间修改，在 dfs 序并不是一段连续的区间，很难做，只能考虑分块。
对于每个块维护数组 \(f_i\) 表示块内的点对 dfs 序为 \(i\) 的点（记为 \(u\)）的影响，即有多少点在 \(u\) 前面，这样做是因为每个点的影响都是一个子树，子树点集在 dfs 序上是连续的。
注意到如果一个点是后序遍历，它不会对任何一个点产生影响，所以只考虑另外两种操作状态。
如果一个块内都是同一种操作状态，显然可以简单预处理维护，这要求修改区间完全包含它。
那么就考虑散块的情况，此时修改区间和它相交不包含，此时只能重构。
为什么重构复杂度是对的，每次修改至多需要重构两个散块。
此时需要构建一个新的 \(f\) 数组，块内的 \(\sqrt{n}\) 个点都将对其进行区间加法。
那么就是一共 \(q\sqrt{n}\) 次修改，\(q\) 次查询，用值域分块平衡一下复杂度即可（修改 \(O(1)\)，查询 \(O(\sqrt{n})\)），而散块共用同一个值域分块，整块可以 \(O(1)\) 查，所以查询是 \(O(\sqrt{n})\) 的。