CF2138 (Round 1048 Div. 1)
20250908
CF2138A
正难则反。注意到到达状态 \((x,y)\) 的方案在 \(x\neq y\) 时唯一确定，我们只要倒推到 \(x=y\) 就好了。
CF2138B
fun fact：赛时几乎所有人都对着错误的题面想出了正确的做法 /xk
因为只有恰好一次使用 \(2\) 操作的机会，所以如果出现 \(3,2,1\) 这样的情况就不合法。
然后维护 \(pre,nxt\) 表示 \(2\) 前第一个 \(3\)，\(2\) 后第一个 \(1\) 的位置，然后维护 \(R_i\) 表示 \([l,r]\) 合法当且仅当 \(r\leq R_l\)。
CF2138C1,C2
注意到最优方案是让 \(lcs\) 是根到某一层的连续路径。
然后相当于做一个背包。
无脑做法是每做一层都判断一下当前背包是否合法，复杂度 \(O(\frac{n^2}{w})\)，已经可以通过 C2。。
进一步思考，设 \(m=\min_{i\in leaf}dep_i\)，则 \(ans\in\{m-1,m\}\)。
所以只要背包做到 \(m\) 的时候判定是否合法即可。
然后可以不断二进制分组做到 \(O(\frac{n\sqrt{n}}{w})\)。