这篇文章受密码保护，输入密码才能阅读

这篇文章受密码保护，输入密码才能阅读

题面(CH暂时无法访问) 为了划分出最少的段数, 我们必须使每一段在校验值不超过T的前提下尽可能长. 以一段的开头为L, 结尾为R, 于是问题就转化成了已知L的情况下怎样找到一个尽量大的R使校验值不超过T. 为了求出校验值, 要对序列进行排序. 因为序列越长校验值一定越大, 我们可以考虑在区间L~N上二分, 但是T很小时, R可变化的范围其实比较小…

复习板子. 远古代码概不负责. ST表基于二进制划分思想, 用于求静态RMQ, $ O(N\log N)$预处理, $ O(1)$查询. 设$ max[i][j]$表示区间$ [i,i+2^j-1]$的最大值, 即从$ i$开始长度为$ 2^j$区间的最大值, 类似于树上倍增. 这个数组很容易预处理出来, 有DP方程$ max[i][j]=max(…

复习下树上常见算法... 本文中都是远古代码, 一切Bug概不负责. lca最暴力的求法就是x,y一次次往上跳, 这样效率显然很低, 考虑优化, 有两种途经: 树上倍增 dfs预处理一个倍增找父亲节点的数组, x,y成倍的往上跳, 时间复杂度降为log级 通常树上倍增的套路都是设$ F[i][j]$为节点$ i$的第$ 2^j$个父亲, 那么有$ …