线段树二分 - 洛谷保存站

## 简化题意：

给定一个初始为零的序列$a_i$，有$Q$次操作，第$i$次操作给定$x_i$和$k_i$，选定$a$的前缀$a_1 \sim a_{x_i}$，并重复以下操作$k_i$次：

选择区间内最小数并加一，若有多个值相同的数，则选择位置靠前的

## 解题思路

不难发现，由于每次操作均选择的是一个前缀，且优先选值小的增加1，因此整个序列应该是单调不增的

因此，每次操作等价于选择$a$中以$a_x$结尾的一个后缀，将其填平，然后把剩下的不够一行的靠着左边填上

考虑线段树维护区间最大值，区间和，并二分答案，找到以$a_x$为结尾的后缀中区间最大值乘以区间长度减去区间和小于等于$k_i$最长的一段，用区间覆盖即可解决

先二分一个答案再区间查询，复杂度$O( n log ^ 2 n )$

## 优化：线段树二分

线段树二分的思想也即把二分放到线段树上进行，在线段树递归的过程中尝试确定答案所在的左右子区间，并递归查找。具体地，以本题为例，我们实现以下算法

1.我们先不断递归左子树，直到线段树的分治中心($mid$)在$a_x$的左边

2.由于查找的是后缀，因此我们先尝试将整个右区间( $a_{mid+1} \sim a_x$）填入作为答案，若发现整个右区间填入为合法，则说明答案在当前分治中心左侧或恰好在右半区间左端点$(mid +1)$，则继续递归左半区间查找答案；否则说明答案在右半区间，我们继续递归右半区间查找答案

3.重复过程$2$，直至叶子节点判断后返回

## 实现：

非常好写，仅比普通线段树查询略有改动

设$now$为当前已经填入的区间区间和，其余代码中变量定义与上文相同

```
inline int search( int i, int l, int r, int x )
{
	if( maxv[i] * (x -l +1) -sum[i] -now <= k ) 
		{ now += sum[i]; return l; } //若当前区间合法，则返回当前区间左端点
	if( l == r ) return r +1; //若递归到叶子节点仍不合法返回区间右端点 +1
	if( x <= mid ) return search( xl, x ); //选定区间在分治中心左侧，递归左子树
	int res = search( xr, x ); //先尝试填入右子树
	if( res == mid +1 ) return search( xl, x ); //若右半区间全部填入合法，递归左子树查找
	return res;  //否则答案就在右区间
}

正在渲染内容...