P6020 [Ynoi2010] Exponential tree 解题报告：
更好的阅读体验
感觉还是水平不太行，写的很感性。
题意
给定 n,k，构造矩阵满足：
-
- 对于 i>j，a_{i,j}=0；
- 若 j>i+1 且 a_{i,j}=1，则存在 i<t<j 满足 a_{i,t}=a_{t,j}=1；
- 矩阵 A^k 需满足对于所有 i\leqslant j，(i,j) 非零。
数据范围：
## 分析
~~之前学习过[相关知识](https://www.luogu.com.cn/blog/qwaszx/jing-tai-ou-jian-jie-ge-lv-xin-xi-zha-xun)，结果又不会了，属实是菜。~~
记 $F(k,n)$ 为在 $(k,n)$ 约束下我们做到的 $m$ 大小。
赋予矩阵一个组合意义：我们初始拥有 $n-1$ 个区间 $[i,i+1]$，需要预处理若干个区间，使得预处理的区间都可以表示成两个更小的预处理区间的无交并，且所有的区间都可以表示成不超过 $k$ 个预处理的区间的无交并。
$k=2$ 时是经典的猫树算法，这里不赘述，可以做到 $F(2,n)=O(n\log n)$，事实上这也是这个子问题的[下界](https://www.luogu.com.cn/blog/EntropyIncreaser/noi2022-count-analysis)。
$k=3$ 时是经典的 sqrt-tree 算法，做法大概是对序列分块，预处理所有块前缀、后缀区间，以及所有整块区间，块内的区间作为子问题递归处理，得到 $F(3,n)=O(n\log\log n)$。
$k>3$ 时，想做到更优，我们需要对整块区间也作为子问题处理。
具体地，我们可以通过 dp 找出最优的分段点：（令 $a_{1,2,\cdots,p}$ 为每一个块的大小）
$$F(k,n)=\min_{a_{1,2,\cdots p}}(a_1-1)+\sum_{i=2}^{p-1}(2a_i-3)+(a_m-1)\\+F(k-2,p-2)+\sum_{i=1}^p F(k,a_i-[i>1]-[i<p])$$
直接求复杂度太劣，剪一剪枝大概就能过了。
---
稍微提一句，当 $k=O(\alpha(n))$ 时，我们可以做到 $F(k,n)=O(n\alpha(n))$（应该是下界？），做法大概是：
建立 $t$ 层数据结构，其中第 $i$ 层数据结构块间用第 $i-1$ 层数据结构维护（我们钦定第 $0$ 层的数据结构为猫树），块内递归下去。
令 $T(t,n)$ 为第 $t$ 层数据结构的深度，我们第 $i$ 层数据结构按照 $T(i-1,n)$ 分块，于是 $T(1,n)=\log^*n$，$T(2,n)$ 就是 $n$ 不断取 $\log^*$ 直到变成 $O(1)$ 的次数。那么 $t$ 就是 $n$ 不断变成 $T(t-1,n)$ 变成 $O(1)$ 的次数，此时 $t=\alpha(n)$，为反阿克曼函数，于是得到 $F(k,n)=O(n\alpha(n))$。
## 代码