牛逼题。
solution
首先来推一推性质。假设我们现在有一个合法的集合，覆盖了 \([1,S]\)，显然新加进去的数 \(i\) 不能 \(\geq S+2\)，而如果 \(\leq S+1\) 那么 \([1,i+S]\) 显然可以被覆盖到。因此有一个 \(O(n^2)\) 的 dp：设选到了第 \(i\) 个数，总和为 \(j\) ，要求 \(j\geq i\)。
这个 dp 状态是两维的，没前途。考虑容斥，枚举第一个不合法的位置设为 \(i\)，那么 \([1,i-1]\) 应该完全覆盖了 \([1,i-1]\)，然后 \(i+1\) 没选，之后的任意。这样子我们发现我们只需要知道 \(f_i\) 表示 \([1,i]\) 完全覆盖了 \([1,i]\) 的方案数即可。
现在状态降低了，但是转移还是 \(O(n^2)\) 的。考虑 \(f_i\) 转移乘的系数是一个整数划分的性质，不妨仿照那个东西的方法，设 \(g_{i,j}\) 表示选了 \(i\) 个，总和为 \(j\) 的方案数。因为选的数互不相同，因此 \(i\) 是 \(O(\sqrt n)\) 的。这样就可以 \(O(n\sqrt n)\) 计算出 \([1,i]\) 中选若干个数加起来为 \(i\) 的方案数。
然后考虑把容斥的 \(-f_j\) 加进去，这需要枚举选的个数 \(i\) ，然后初始值 \(i(j+1)+j\)。 但是这里有一个问题，\(f_j\) 的计算依赖于前面，但是计算 \(f_j\) 的时候需要将 \([1,j-1]\) 都加入 dp 中，时间复杂度不能承受。
考虑分治，每次只计算左半边对右半边的贡献，这样就可以一次性将左半边加入 dp 中，时间复杂度 \(T(n)=2T(n/2)+O(n\sqrt n)\) ，解得 \(T(n)=O(n\sqrt n)\)。
但是实际上这样子常数非常大。注意到如果 \(f_j\) 要转移到 \(f_{i}\)，那么 \(j\) 要选一个， \(\geq j+2\) 的也要选一个，因此 \(f_j\) 向 \(f_i\) 转移要求 \(2j+2\leq i\)，也就是说分治的时候右半边区间内是不会转移的，这样子时间复杂度计算就是 \(T(n)=T(n/2)+O(n\sqrt n)\) ，常数比较小。
标签：geq,半边,luogu,P8340,sqrt,转移,AHOI2022,复杂度,dp From： https://www.cnblogs.com/275307894a/p/17406079.html