啥,又是主席树?连续三场比赛都有主席树,然后都不会。。
题意
给你一个序列, 告诉你L,R,P,K,让你求在L,R这段区间内,P与区间内数字的距离的第K小值
思路
求第K小,自然是主席树,但是这里并不单纯是求原序列的第K小,而是距离的第K小,然后我就母鸡了。其实有时候我们求第K小值还可以用二分,枚举上下界,第K小值满足的条件是有至少K个数字小于等于这个数。然后就二分就OK了。那么在这里,我们枚举距离值,那么我们就看看在这段区间内是有多少个数字是 在P - 距离 到 P + 距离的,如果大于K,就要缩小这个距离,我们要求的是那个最小的区间内数字个数等于K的那个数字。主席树在这里的应用就是给你一段区间,让你求这段区间内大于A小于B的数字的个数。这道题我以前用的是离散化,查询时按照地址查询,这里就用按值查询,很简便。
1 |
|