一个区间,设其为 [l,r][l,r][l,r],然后每两个数有一个值是 f(a,b)f(a,b)f(a,b),然后求其前 kkk 大
我的思路:
令二元组集合为 SSS,每次用线段树求出这个区间的 max{f(i,j)}\max\{f(i,j)\}max{f(i,j)},然后将 (i,j)(i,j)(i,j) 从 SSS 中删除,继续求其 maxmaxmax
这里的问题是,怎么将 i,ji,ji,j 删掉,老师说有个经典套路是拆区间,但是我不理解为什么
就是 [l,r][l,r][l,r] 中有两个点 i,ji,ji,j 且 i<ji< ji<j,然后拆出很多个区间可以类似于把 (i,j)(i,j)(i,j) 从 SSS 中删去
哪位大佬会,请讲清楚点,谢谢,可以给个关注