小衣同学的博客

由于是sum[i]-sum[j]>=mid，i-j为质数，所以需要i-j是质数且sum[j]尽可能小。二分答案mid，能用最早的段达到mid则用最早的段达到，所以set维护前缀和及其下标。由于每n个数有n/logn个质数，所以期望意义上每logn个数会有一个质数。那么，用set维护没用过的前缀子段，set上暴力遍历若干个最小的值即可。随机是为了质数这个限制条件而生的。最大化min还是逃不出二分，

这个就是从前面第一个[a[i],a[i]+k]和前面第一个[a[i]-k,a[i]]的值转移。一个暴力的想法，是求满足相邻项差值不超过k的子序列最大长度，然后用权值线段树二分，当时转移是从前面>=a[i]和<=a[i]最接近的值转移。其实与泽与老师院赛那个题很像，求abs的最小值的dp，复杂度是O(sumq nlogn)的，不能接受。预处理找到这些位置之后，每次现dp即可。然后考虑优化掉这个logn的转移，

（9）新增L型条，使每种颜色（7）（8）两部分连通，至此所有颜色已完全连通。（5）对于奇数行，z轴正向多出来的这k层，每一层填充k种颜色中的一种，（6）对于偶数行，x轴正向多出来的这k层，每一层填充k种颜色中的一种，这样可以使得原来偶数行的原图里的颜色，和本次新增的奇数行的部分连通，这样可以使得原来奇数行的原图里的颜色，和本次新增的偶数行的部分连通，（7）沿z轴正向，k种颜色每种颜色分配一个平行y轴的长条，（8）沿x轴正向，k种颜色每种颜色分配一个平行y轴的长条，（4）奇数行，x轴正向伸长为n+k。

l为重链头的dfs序，r为叶子重链尾的dfs序时，这个区间节点对应的(a,b)中a的值。由于为0的值会对运算值有影响，并且儿子f值从一个0变成没有0的时候难以恢复之前的乘积，基本是对于有根树树形dp，想动态获取根节点的dp值，dp值和树上点权相关，点权带修，所以单独记录0的个数，所以变更的时候，动态记录链头点的f值为0的儿子的数量。其中，b是f值非零的轻儿子的f积，x是重儿子的f值（未知，待代入）递归到叶子的时候，由于叶子不存在重儿子，x值为0，所以链头的f值，就是当线段树区间[l,r]，