T1
个人思路：
询问：求 \(1\) 到 \(t_i\) 路径上离 \(1\) 最远的 \(p\)，使得 \(dis_{1,p} \times 2 \le d_i\)。即 \(dis_{1,t} \times 2 \le d_i + dis_{p,t} \times 2\)。
等价于：\(dis_{p, t} \ge dis_{1,t} - \lfloor \frac{d_i}{2} \rfloor\)。
维护从 \(u\) 往上走 \(2^j\) 步的距离，倍增往上跳。
T2
对于固定前缀 \(T_{1\sim i}\)，第 \(i+1\) 次操作所有方案都对答案有贡献，新生成的前缀互不相同。
我们把 \([1,m]\) 和 \([m,1]\) 看成一段可插入的区间，可以插入 \(2\sim m-1\) 各一个。\([1,1],[m,m]\) 不可插入。
状态：\(dp_{i,j,0/1}\) 表示前 \(i\) 次操作，有 \(j\) 个可插入区间，结尾为 \(1/m\) 的方案数。
初始化：\(dp_{0,0,0} = 1\)。
转移：炸裂，因为需要储存当前剩余可填的位置，再加一维直接 GG。
但是可以储存已经填掉的数的个数，即 \(dp_{i,j,k,0/1}\) 表示前 \(i\) 次操作，有 \(j\) 个可插入区间，填入 \(k\) 个数，结尾为 \(1/m\) 的方案数。状态 \(\Theta(n^3)\)，时间复杂度 \(\Theta(n^3)\)。
如果不考虑 \(1,1\) 和 \(m,m\)，也就是说，只填和上一个结尾不同的数。
最后计算答案时，我们把这些 \(1,1\) 和 \(m,m\) 补回去。好像可以。
状态：\(dp_{i,j}\) 表示表示前 \(i\) 次操作，有 \(j\) 个可插入区间。即插入了 \(i-j\) 个数。
转移：\(dp_{i,j} = dp_{i-1,j-1} + dp_{i-1,j} \times (j \times (m-2) - i + j + 1)\)。注意，需要满足 \(j * (m-2) \ge i - j\)。
答案：
把 \(n - i\) 个数分配给 \(i + 1\) 个点，允许有点为空，插板方案为 \(C_n^i\)。
寄了，过不去样例 \(3\)，去写暴力。
状态：\(dp_{i,j,k,0/1}\) 表示前 \(i\) 次操作，有 \(j\) 个可插入区间，填入 \(k\) 个数，结尾为 \(1/m\) 的方案数。
转移：
上一个填的数相同：\(dp_{i,j,k,0} = dp_{i-1,j,k,0}\)
上一个填的数不同：\(dp_{i,j,k,0} = dp_{i-1,j-1,k,1}\)
上一个插入：\(dp_{i,j,k,0} = dp_{i-1,j,k-1,0} \times (j\times(m-2)-k+1)\)
合法状态：\(i\ge j\) 且 \(j\times(m-2) \ge k\)。
答案：\(\sum dp_{n,j,k,0/1}\)。
wssb，正解样例 \(3\) 过了，但是样例 \(4\) 卡死？？？
数组开小了。。。
T3
暴力删，删完暴力改，时间复杂度 \(\Theta(n\cdot m^2)\)。
标签：个数,春季,times,插入,ge,2023,CCF,dp,dis From： https://www.cnblogs.com/Mysterious-Cat/p/17134590.html