一些以前遗留的题如果想起来了也写进这吧，总归要整理的。
ARC171
B. Chmax
600 分的 ARC B 确实有点难度。
先理清操作的实际含义：建出 \(i\rightarrow p_i\) 的置换环结构，在置换环上从点 \(i\) 开始走，当下一个点的编号大于自身的时候就走，否则就停下来。然后 \(B_i\) 就代表最后停留的位置。因此比较平凡地，有 \(B_i\ge i\)，且 \(B_{B_i}=B_i\)。
对一个确定的 \(P\) 而言，所有满足 \(B_i=x\) 的人应该维护同一置换环上连续的一段，且这些人应该按照编号升序排布。对于一个 \(x\)，我们把所有 \(B_i=x\) 的称为一类。同一类的数一定紧密相连，升序排列。因此可以看成一个整体。令 \(S(x)\) 是所有 \(B_i=x\) 的位置里最小的 \(i\)。
一个置换环由若干个等价类拼接而成，等价类的拼接需要满足：若在置换环上，等价类 \(x\) 的下一步进入了等价类 \(y\)，那么一定有 \(x\gt S(y)\)，否则当一个数走到 \(x\) 的时候它会选择继续向下走，而不是停留在 \(x\)。
因此，我们可以把对排列计数看成为每个等价类选后继。相当于把等价类看成点，然后对它们的合法置换群计数。
从 \(i:1\rightarrow n\) 扫描，构建一个序列。如果存在某个 \(S(x)=i\)，就加入左括号。如果 \(B_i=i\)，就加入右括号（同时满足两个条件的话先加入左括号）。然后计数的内容变为了：对每个右括号选一个位于之前的左括号匹配的方案数。
因此直接顺序扫描序列，维护一个变量表示当前前缀有多少未匹配的左括号。然后 \(O(n)\) 解决。
C. Swap on Tree
感觉难度很高，vp 的时候写了一个 dp 的做法，发现有纰漏了以后往错误的方向继续想了。第二天来修了一下系数就通过了。究其原因还是想的不够明白。
忽略复杂的交换过程，直接尝试刻画一个最终局面合法的条件。
对于一个点 \(u\) 子树，我们最多只有一次机会，交换 \((u,fa_u)\) 来沟通子树 \(u\) 与外界，因此一个必要条件是，每个子树内最多只有一个外来点。且这个外来点是谁都无所谓，因为它一定是从 \(fa_u\) 换进来的。
这启发我们设 \(f(u,0/1)\) 表示 \(u\) 子树内的最终局面已经确定，是否有一个数会被换出去的方案数。
转移时合并子树信息：令 \(g(c)\) 表示有 \(c\) 个儿子会有数需要换出去的方案数。
这里需要一些分类讨论：
- 若 \(u\) 在原地不动，仅在 \(c=0\) 的时候成立，因为子树之间显然无法进行任何交换了。以 \(1\) 的系数贡献至 \(f(0)\)。
- 否则点 \(u\) 一定经过了交换。考虑 \(u\) 子树内部有点换了出去和没有换出去两种情况：
- 若没有点换出去，则考虑交换只发生在 \(u\) 和儿子处。共有 \(c\) 次交换，调换任意两次交换的先后顺序都会导出不同的结果，因此以 \(c!\) 的系数贡献至 \(f(0)\)，前提是 \(c\ge 1\)。
- 若有点换出去，则考虑实质上就有 \(c+1\) 次交换，较之上一种情况，多出了 \((u,fa_u)\) 边的交换。同样调换任意两次交换的先后顺序都会导致不同的结果，因此有 \(c!\) 的系数贡献至 \(f(1)\)，这里不要求 \(c\ge 1\)。
然后就得到了一个 \(O(n^2)\) 的做法。
E. Rookhopper's Tour
D 题太简单了不写。这个 E 题很有意思。
先进行一些基本的观察分析：\(m\) 肯定是偶数。我们的路线一定是竖直、水平交替。最后一次消除的白棋一定和 \((A,B)\) 相邻。还有呢？
随便按照题面的过程走几步：发现第一步会有竖直水平两种选择，接下来永远只有一种走法可走（甚至可能会无法继续走）。如果路线唯一就好了，因为可以把合法局面计数变成对合法路线计数。事实上任何合法局面也恰好仅有一条合法路线。
如果有两条合法路线，那其实应该是同一条的正反走法。这就要求路线的每一步都可逆。可逆当且仅当黑棋当前位置和下一次移除的白棋相邻。而我们又要求第一次和最后一次移除的白棋都与 \((A,B)\) 相邻，容易发现此时就一定不存在一条可逆的回路。
以下默认第一步竖直走，第一步水平走只需要交换 \((A,B)\) 后计算即可。
接下来就没想明白了，为什么呢？可能是往 dp 想了，然后发现走一步是影响的连续的两行/列，非常难记录进状态里，就 gg 了。
还是考虑忽略过程看最终路线的样貌，这是一个很 ARC 的想法。。
第一步一定是 \((A,B)\) 出发，移除某个 \((x,B)\) 然后走到 \((x-1/x+1,B)\)，然后第二步再水平出发。相当于第一步宣告了有连续的两行有白棋，第二部宣告了连续的两列有白棋。整个路径就是一个 \(\frac{M}{2}\) 次宣告行，\(\frac{M}{2}\) 次宣告列的过程。最后恰好有 \(M\) 行 \(M\) 列被宣告了有白棋，非常完美。
然后来刻画路径从 \((A,B)\) 开始的条件：相当于第一步宣告的行里不能有第 \(A\) 行，第二部宣告的列里不能有第\(B\) 列。
再刻画路径从 \((A,B)\) 结束的条件：相当于第 \(M-1\) 步宣告的行里必须有第 \(A\) 行，第 \(M\) 步宣告的列里必须有第 \(B\) 列。
因此容易看出有解的另一必要条件是 \(M\ge 4\)。考虑枚举第 \(M-1\) 和第 \(M\) 步的具体行动，共有 \(4\) 种可能。
确定了最后两步以后，再来确定前面 \(M-2\) 步的方案数。行、列的选择是完全独立的，只用考虑如何算剩余 \(\frac{M}{2}-1\) 步行操作的方案数：第 \(M-1\) 步选出的两行把棋盘划分成了上下两部分，我们枚举在上半部选择了 \(c\) 个连续的两行，则就应该在下半部分选 \(\frac{M}{2}-1\) 个连续的两行，在 \(n\) 行里选出 \(m\) 个连续的两行的方案数容易使用插板法 \(O(1)\) 算出，再用 \(\binom{\frac{M}{2}-1}{c}\) 作为系数结合上下半部。
还遗漏了一个条件：比如设第 \(M-1\) 步宣告了 \((A-1,A)\) 两行，则实际过程中应该是我们从上半部出发，移除了一个 \((A-1,B)\) 的白棋来到 \((A,B)\)。因此此时要求 \(c\gt 0\) 且d第 \(M-3\) 步的宣告位于上半部。对于宣告 \((A,A+1)\) 两行的情况同理，我们要求第 \(M-3\) 步的宣告位于下半部。因此需要略微修改合并时的组合数系数，以及微调 \(c\) 的上下界。
此时我们就在 \(O(n)\) 的时间内解决了。
F. Both Reversible
这个题更趣味，一定要学会了来补。
现在大致学会了，还有一步的证明没有理解。感觉非常需要观察力，猜想力和踏实的推式子能力，非常牛的题。
可以写一个搜索来观察 \(n\) 较小的时候解的情形：发现 \(n\) 为奇数的时候一定是有非平凡回文循环节，但偶数的时候会有一些例外，比如：$$\text{ababbaab}$$，或者第一个样例中的 $$\text{abab}$$ 也是。
一般而言这种题目里都会需要倒来倒去，充分利用 \(A+rev(B)\) 和 \(rev(A)+B\) 的性质。
比如说，不妨设 \(|A|\le |B|\)，那你发现 \(A\) 必定是 \(B\) 的前缀。因此令 \(B=A+C\)。则 \(A+rev(B)\) 回文等价于 \(A+rev(C)+rev(A)\) 回文等价于 \(rev(C)\) 回文等价于 \(C\) 回文。然后 \(rev(A)+B\) 回文等价于 \(rev(A)+A+C\) 回文。因此令 \(X:=rev(A)+A,Y:=C\)，则相当于我们要求：\(X\) 回文，\(Y\) 回文，\(X+Y\) 也回文。所有合法的 \((X,Y)\)（注意到 \(|X|\) 必须是偶数）。
此时有比较经典的结论是：一定存在一个本原回文串 \(T\) 使得 \(X=T^n\) 且 \(Y=T^m\)（本原指的是说 \(T\) 不存在更小的回文整周期）。
当 \(n\) 是偶数的时候就有，\(A=T^{\frac{n}{2}},B=T^{\frac{n}{2}+m}\)。当 \(n\) 是奇数的时候，首先 \(T\) 的长度必须是偶数，假设其形如 \(rev(S)+S\) 的形式，那么 \(A=S+T^{\frac{n-1}{2}},B=S+T^{\frac{n-1}{2}+m}\)。
对于 \(|A|\gt |B|\) 的情况也同理。最后我们得出，合法的拆分方式一定形如下面两种：
- \(A=T^x,B=T^y\)，其中 \(x,y\) 为正整数。
- \(T=rev(X)+X,A=X+T^{x},B=X+T^{y}\)，其中 \(x,y\) 为非负整数且 \(X\neq rev(X)\)。
到这里也能和最开始的小观察吻合：下面一种 case 得到的串长度始终为偶数，所以 \(n\) 为奇数只有上面一种 case 的还存在。
并且注意到：第一种方式得到的串一定自身回文，第二种方式得到的串一定自身不回文。所以首先两种拆分方式独立。
第一种情况非常容易，枚举一下 \(|T|\) 然后做一个倍数容斥即可。
第二种情况的话，首先一个很重要的事情是，任何一个非回文串至多会有一种合法拆分方式。证明尝试理解失败了。可以打表猜测？
然后对串计数就变成了对拆分方式计数：自然的想法是枚举 \(x=|X|\) 然后显然 \(x\mid n\) 且 \(\frac{n}{x}\) 是偶数。然后我们把原串划分成了 \(\frac{n}{x}\) 段，枚举一个奇数编号的段 \(i\)，然后就是说 \(A\) 由前 \(i\) 段组成，\(B\) 由后面的段组成。那么每一段到底取 \(X\) 还是 \(rev(X)\) 也已经知晓。此时我们合并等价类后得到了一个 \(O(x)\) 的数组 \(b\)，\(b\) 的每个位置要么被钦定，要么是问号。然后需要计数的是：有多少种可能的 \(b\) 使得 \(rev(b)+b\) 是本原的。这部分的复杂度是 \(O(d(n)\times \frac{n}{x}\times x)\)，我的实现比较烂，多带了 \(\Sigma\)。所以是 \(O(nd(n)\Sigma )\)。
然后接下来本原这个事情考虑就容斥掉：枚举一个 \(2x\) 的约数 \(z\) 满足 \(\mu(\frac{2x}{z})\) 不为 \(0\) 即可。然后容易 \(O(x)\) 计算方案数。
这样的话，这部分的复杂度是 \(O(d(n)\times\frac{n}{x}\times d(x)\times x)\) 也就是有一个理论上界是 \(O(nd(n)^2)\) 的，但显然跑不满。然后可以通过此题。
IOI2023
在冬令营的时候听了国家队的讲课，觉得这一场的题目相比 2022 更为贴近 CNOI，还是很有做的必要的。
Day1 T1. 封锁时刻
这个题还在我的能力范畴内。
令 \(f_u\) 是 \(u\) 到两个起点较近的距离，\(g_u\) 是较远的。容易想到抽象成以下问题：
- 对于每个点 \(u\)，付出 \(f_u\) 的代价可以获得 \(1\) 的收益，付出 \(g_u\) 的代价可以获得 \(2\) 的收益（\(f\le g\)）。要求总代价 \(\le k\) 且收益最大。
理由是这是一个经典的问题。然而这个转化有误：由于我们把点独立开了，就先需要证明我们若选了一个决策，则在原图上其前驱决策也被选了。
前驱决策的定义：比如说，我们若把 \(u\) 调成了 \(Y\) 可达，则考虑 \(Y\rightarrow u\) 的路径上的倒数第二个点 \(v\)，其一定也被调为了至少 \(Y\) 可达。不难发现前驱决策的代价一定不大于当前决策。
讨论后会发现唯一的问题出现在，\(X\) 到 \(Y\) 的路径上，中点的两侧。设两个点为 \(p,q\)。则 \(g_p\) 的前驱决策是 \(f_q\)。
对于其余的情况，\(g_u\) 的前驱都是 \(g_v\)。所以如果你没有选 \(g_v\) 一定不会选 \(g_u\)。但是现在，我们可能会出现不选 \(f_q\) 就去选 \(g_p\) 的情况，毕竟前者收益仅为 \(1\) 而后者收益为 \(2\)。
当意识到这个仅存的特殊情况后，补丁就很容易打了：当我们让某个点同时能被 \(X,Y\) 可达时，两点之间路径上的点一定都会先设置成至少为 \(f\)。所以我们讨论一下是否有人选择了 \(2\) 的收益。若没有，则等价于把 \(g\) 全设为 \(\infty\)。若没有，则等价于对于每个 \(X,Y\) 之间的点 \(u\)，都先付出 \(f\) 的代价获得 \(1\) 的收益，然后令 \(f:=g-f\)，\(g:=\infty\) 即可。
现在再来回顾”经典问题“是如何解决的。常规做法是反悔贪心 / 模拟费用流。还有一个更简单的做法：
当 \(f\le g-f\) 的时候，我们可以把一个点拆成两个点，选了收益为 \(1\)，代价分别为 \(f/g-f\)。
当 \(f\gt g-f\) 的时候，我们把一个点设置成了 \(f_u\)，那再花费更小的额外代价就能设置成 \(g_u\) 多获得 \(1\) 的代价。换言之就是，只有最多一个 \(u\) 会选择成 \(f_u\)，剩下的要么不选，要么选成 \(g_u\)。我们枚举这部分里有 \(k\) 个选了 \(g_u\)，则一定选的是 \(g\) 最小的 \(k\) 个。剩下的点和第一类混在一起按照 \(f\) 排序，然后贪心地能选就选即可。上述过程使用线段树维护就容易做到 \(O(n\log n)\)。
Day1 T2. 最长路程
这个题就不是我的范畴内了，只能说非常厉害。
由于这个图非常稠密，任意三点之间都有一条边。先猜测其是连通的，发现只有一个反例是两个完全图的情况。再猜测对于一个连通块，一定能找到一条哈密顿路。
考虑使用增量法构造。同时维护两条路径，分别记作 \(u\rightarrow v\) 和 \(p\rightarrow q\)，然后考虑现在加入一个点 \(x\)。
\((v,q,x)\) 三者之间必定有一条边。如果是 \((v,x)\) 或 \((q,x)\) 就直接把 \(x\) 接上。否则 \((v,q)\) 有边，本来的两条路径合并成一条，新的第二条路径为 \(x\rightarrow x\)。
最后把所有点划分成了两条路径，如果两条路径直接无交那就是两个连通块的情况，输出较长路径即可。否则我们再将其拼接成一条哈密顿路。
假设 \(u\neq v\)。然后 \((u,v,p)\) 三者间必定有一条边。若这条边是 \((u,p)\) 或 \((v,p)\) 直接就能拼接。否则说明第一条路径其实是回路。
对第二条路径做同样的事情，然后现在我们得到了两个回路而不是路径（认为大小为 \(1\) 的路径也算回路）。
两个回路直接的拼接非常容易，我们只需要求出一对具体的 \((x,y)\) 满足 \(x\in u\rightarrow v\) 且 \(y\in p\rightarrow q\) 且 \((x,y)\) 有连边即可。这可以两次二分出。然后我们得到了一个 \(2(n+\log)\) 的做法。还无法通过。
考虑 \(2n\) 已经大于 \(400\) 了，必须优化这里。尝试用 \(3\) 次操作加入两个点。事实上也是可以做到的。假设我们目前尝试加入 \((x,y)\)。
-
若 \((x,y)\) 有连边。
此时考虑 \((v,q,x)\) 三者，若存在 \((v,x)\) 或 \((q,x)\) 的边直接拼接即可。否则存在 \((v,q)\) 的边，依旧是原先的两条路径合并为一条，新的第二条路径为 \(x\rightarrow y\)。
-
若 \((x,y)\) 无连边。
此时 \((x,v)/(y,v)\) 必定存在一条。不妨假设 \((x,v)\) 存在。然后 \((x,q)/(y,q)\) 必定存在一条。哪种情况都能合并成两条路径。
然后我们在 \(1.5n+\log\) 的次数内解决了本题。
Day1 T3. 足球场
这个题的思维难度没有上一题高，但是在实现上需要精细思考。
先刻画一下一个连通块合法的充要条件：
首先是，若两个同行的点被选中，他们之间不能有未选中的点。同列的两个点同理。因此这是个凸包状物的结构。
思考一下发现并不充分：如果是一个两行的图形，并且区间的位置关系是相交但不包含，比如第一行位于 \([1,3]\) 第二行位于 \([3,5]\)。同样无法在两步内从 \((1,1)\) 走到 \((2,5)\)。这两行不需要相邻，只要存在这样的两行就一定不合法。因此得出一个更强的约束：对每一行，把占据区间提取出来，任意两个区间必须是包含关系，并且从上往下看，区间长度一定是先递增再递减的。此时也不难验证充分性。到这里图形的约束已经非常强了。
然后考虑直接 dp：设 \(f(x,y,l,r)\) 表示我们限定图形范围在行 \([x,y]\) 内，且长度最小的那一行区间是 \([l,r]\) 能得到的最大图形。
转移的时候枚举是第 \(x/y\) 行的区间为 \([l,r]\)，然后转移到 \(f(x,y-1)\) 或者 \(f(x+1,y)\) 的 \([l',r']\) 状态上去，满足 \([l,r]\subseteq[l',r']\) 即可。
这样我们需要算出某个 \(f(x,y)\) 后对他的信息做二维前缀 \(\max\) 来 \(O(1)\) 转移。复杂度 \(O(n^4)\) 还是太慢。
考虑优化状态数：固定 \([x,y]\) 以后 \([l,r]\) 一定满足：第 \(x\sim y\) 行上，\([l,r]\) 范围内都是空地。令 \(b_c\) 表示 \(x\sim y\) 行内第 \(c\) 列是否全为空地。则条件可以表述为 \(b_{l}\sim b_{r}\) 全为 \(1\)。注意到 \([l,r]\) 应该贪心地取到一段极长的 \(1\) 的连续段，这样的话固定 \([x,y]\) 后就只有 \(O(n)\) 个状态。状态数缩减到 \(O(n^3)\)。
还能继续优化：我们只固定 \(x\)，然后如果一个 \((y,l,r)\) 满足说，第 \(y+1\) 行的 \(l\sim r\) 列依旧都是空地，那么它就不是极大的。或者说第 \(x\sim y\) 行的第 \(l-1/r+1\) 列都是空地，那么也不是极大的。然后极大的状态应该只有 \(O(n)\) 个：令 \(b_c\) 表示从第 \(x\) 行开始，第 \(c\) 列的第一个障碍位置。那么 \((y,l,r)\) 合法当且仅当 \(y\) 是区间里 \(b\) 的最小值减一，且 \(b_{l-1}/b_{r+1}\) 都小于这个区间最小值。那么很显然就能分析出只有 \(O(n)\) 个极大状态了。 这样我们就保留了 \(O(n^2)\) 个极大状态，那么转移呢？
只对每个极大状态存储 dp 值。讨论到底是第 \(x\) 行的区间等于 \([l,r]\) 还是第 \(y\) 行的区间等于 \([l,r]\)。
对于前者，我们应该转移到某个 \((x+1,y,l',r')\) 上去。对于后者，我们应该一口气把第 \(y\) 行这边的，连续极长的只能取 \([l,r]\) 的行全部选了。也就是 \(\ge \max\{b_{l-1},b_{r+1}\}\) 的行。然后转移到某个 \((x,y',l',r')\) 上去。
固定 \((x,y)\) 以后，所有的极大状态里 \([l',r']\) 肯定都是不交的。所以对于 \(x/x+1\) 和每个 \(y\)，把所有极大状态按照 \(l'\) 升序排序并储存其 dp 值。然后询问的时候只需要二分查找一次，就是 \(O(n^2\log n)\) 的复杂度。可以轻松通过。
Day2 T1. 山毛榉树
可以说是本场比赛最为 ad-hoc 的题，遇到这种脑力体操只能说自求多福了。
首先绝妙置换应该是一个拓扑序。同时一个节点不应该有两个相同颜色的儿子，因为这两个儿子的 \(f\) 不同而父亲相同。
对于一个固定的颜色 \(c\)，考虑所有颜色为 \(c\) 的儿子，由于 \(f\) 是递增的，所以一定是一段前缀，有颜色为 \(c\) 的儿子。
考虑对于两个点 \(x,y\)，\(x\) 先于 \(y\) 出现。然后对于一个儿子的颜色 \(c\) 只有三种情形：都有，都没有，\(x\) 有 \(y\) 没有。后两种情况平凡，对于第一种情况，我们会要求 \(x\) 的儿子先于 \(y\) 的儿子出现。那么也就是递归定义了一个偏序关系的存在：
\[cmp(x,y)=\prod_{c}[cmp(son_{x,c},son_{y,c})] \]当然这里忽略了不能有 \(x\) 没有但 \(y\) 有的颜色，这个是容易判断的。
然后我们断言说置换合法等价于任意相邻的点都满足 \(cmp\) 这个偏序。容易说明充分性。
但是你这个判断不能真 dfs 下去，肯定复杂度爆炸。发现 \(cmp\) 成立的必要条件是 \(sz\) 有偏序关系。那么我们按照 \(sz\) 先排序。然后 check 的时候只需要比较儿子颜色集合是否相同，以及儿子的 \(sz\) 是否有偏序关系即可。
然后就启发式合并一下就 \(O(n\log^2 n)\) 了。
Day2 T2. 超车
这个题还是比较平凡的，也很吃实现功力啊啊啊。
首先题目其实已经给你转化好很多东西了：最朴素的想法是每次询问重新做。然后按照题面里的过程模拟，也就是按照到达时间为第一关键字速度为第二关键字的顺序排序，然后求前缀到达下一个站的时间的 \(\max\)，这样就是 \(O(qmn\log)\) 级别的。
然后说，我们不需要每次把备用车塞进去，因为备用车影响到的车，一定速度都比他快，那么这些车都不会影响备用车。
换言之就是，你直接预先把 \(n\) 辆一般车求一遍每个站的到达时间。然后一次询问的时候就直接 \(O(m)\) 扫每个车站，二分+求前缀 max 就可以求出到下一个车站的到达时间，这样的话复杂度是 \(O(n^2\log+qm\log)\) 级别的。已经能通过除了最后一个子任务以外的所有测试点。
进一步的话考虑只能是预先求出每个 \(y\) 对应的答案。就是维护那种 \(ans(y)\) 的数组之类的。因为这东西交互等价于强制在线，也没有什么离线下来的说法。那就考虑最初 \(f(y)=y\)。到达一个车站继续走的时候，对于 \(n\) 俩车，他们应该有一个管辖区间 \([l,r]\)，就是当 \(y\in [l,r]\) 的时候，对应的前缀 max 是这一辆车。然后会把这个区间的一个前缀强行赋值成前缀 max，剩余部分不变（因为它们的到达时间自身就大于前缀 max 了）。所以每个 \(f(y)\) 都是关于 \(y\) 的一个一次函数。这是我们的大致过程，容易想到用类似颜色段均摊的方式，set 维护。每一段的 \(f\) 都是一个固定的一次函数。
那么一个问题是，你枚举了一辆车怎么快速找到它的管辖区间？可以在平衡树上二分，太不牛了。对每个连续段把它的结尾的 \(f\) 扔进一个 map 里然后在 map 上二分一下就能找到第一个被管辖到的连续段，这个写法比较方便。
时间复杂度即为 \(O(n^2\log+q\log)\)。
Day2 T3. 机器人比赛
呃呃这个题先咕了。