1. 题目

传送门= ̄ω ̄=

2. 题解

这,,,是我写的第多少个区间kth问题的算法&代码了???

列举一下QvQ:

  • 分块
  • 二分套线段树
  • 主席树
  • 二分套线段树套splay(资磁修改)
  • 整体二分

QvQ

痛苦不堪。

整体二分个人感觉就是二分答案の升级版。

一般的二分答案做这题的话,就是对于每个询问,二分一个答案,然后去线段树里查询这个答案的排名,在确定这个询问的答案是小于还是大于(或等于)这个二分出来的答案,最后得到准确答案。

而我们的整体二分则是先把所有询问&修改按输入顺序存好(初始序列视为n次修改),然后一起二分答案。

二分一个答案以后,我们可以把所有询问分为两部分:答案小于二分出来的答案的询问和大于二分出来的答案的询问。

至于修改操作,我们可以判断:如果这个修改的值是小于二分出来的答案的,就说明这个修改会影响询问的分类,我们就执行这些修改,等把询问分完类以后再修改回来。执行修改在这题中可以用树状数组维护!这个树状数组维护着每个区间内小于等于二分出来的答案的数字有多少个。

具体怎么分类呢?我们对于每个询问,都查询一下在这个询问的区间内,小于等于二分出来的答案的数字有多少个,如果小于等于二分出来的答案的数字个数是大于等于这个询问对应的k的,则说明这个询问的答案是小于等于二分出来的答案的,否则说明是大于二分出来的答案的。

于是我们就成功分好类啦!

然后在递归,整体二分两个分类的询问即可。

具体看代码吧,我也是看代码才看懂的,毕竟语言的表达还是赶不上直观的代码。

代码: