10.8-10.9：
whk
10.10
专题。
CF1798E Multitest Generator：直接做就行，发现答案至多为 \(2\)。
CF2066C Bitwise Slides：我们维护那两个相同的数，再 dp。
CF431D Random Task：发现答案满足单调性，可以二分+数位 dp 简单求解。
假设 \(n_1=n,n_2=n+1\)
\([n_1+1,2n_1]=[n+1,2n]\)
\([n_2+1,2n_2]=[n+2,2n+2]=[n+2,2n]+[2n+1,2n+1]+[2n+2,2n+2]=[(n+1)<<1,(n+1)<<1]+[n+2,2n]+[2n+2,2n+2]=[n+1,2n]+[2n+2,2n+2]\)
证毕。
P4739 [CERC2017] Donut Drone
我们显然有一个 \(O(n^2 \log^2{n})\) 倍增的做法，在 \(8s\) 时限下可以通过。
考虑优化。
我们将 \(k\) 步拆为：\((sx,sy) \to (x1,1) \to (x2,1) \to (ex,ey)\)
显然 $(sx,sy) \to (x1,1) $ $ \to (x2,1) \to (ex,ey)$ 可以暴力跳
为维护 $(x1,1) \to (x2,1) $ ，我们对列建线段树，对于每个区间 \([l,r]\)，记录 \(dp[p][x]\) 表示线段树第 \(p\) 个节点的 \((x,l)\) 这个点跳到 \(r+1\) 列，跳到那个点的横坐标。
在对于每个 \((x,1)\)，使用倍增记录跳 \(2^k\) 圈之后跳到那个点的横坐标。
时间复杂度 \((n^2 \log n)\)。