尺取+线段树
Soldier Game
题目链接:https://codeforces.com/gym/104270/problem/I
题意:给定一个序列$a_n$,要求将序列划为若干组,每组由一个或相邻的两个元素组成,组的权值就是组内元素的权值之和,每个元素在且仅在一组内,要求一种分组方式,使得组之间的极差最小.$n\in(1,1e5)$
分析:序列最值首先考虑二分,然而知道了极差并不能直接得到一组合法的构造方式,必须明确上下界.如果用二分套二分来得到上下界,其实也不能很好的告诉你如何划分序列,比如在一个数归属左右都可以,但是会影响后面的取值的情况里,单纯从一个方向构造不一定有合法解.
传统的最值转化判定的思路行不通,只能另辟蹊径.考虑分组操作的实质,就是用一些小线段对整个区间进行覆盖,如果这些线段能恰好完全覆盖整个区间,那么就可以构成一组合法解.
思路似乎已经明确,将原序列分为长度为1,2的子段,排序后从小到大枚举权值最小的线段,并向后合并直到原区间被完全覆盖,最后比较每次的权值极差就得到答案.
不过可能出现一种情况,线段$ [ a_{i-1},a_i] , [a_i,a_{i+1} ] $,同时存在,但$a_{i-1},a_i,a_{i+1}$没有其他的覆盖.如果每次只存覆盖次数,就无法处理这样的情况.
考虑重新设计状态,$sum[p][0/1][0/1]$表示所辖区间的左右端点分别在长度为$1/2$的线段内是否全覆盖.那么可以得到线段树式的转移1
sum[p][i][j]=(sum[ls][i][0]&sum[rs][0][j])|(sum[ls][i][1]&sum[rs][1][j]);
$sum[1][0][0]$就表示整个序列是否被完整覆盖.
维护一个单调指针,对于每个确定的最小值线段,找到最小的上界线段满足全覆盖,记录极差,算完后再将当前的最小值线段删掉.单调指针和下界都是会访问连续的n个值,线段树每次修改$logn$,总复杂度$O(nlogn)$,可以通过本题.