关于数据结构的套路
  • 板块学术版
  • 楼主Phrvth
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/10/1 09:02
  • 上次更新2023/11/2 16:51:31
查看原帖
关于数据结构的套路
520544
Phrvth楼主2023/10/1 09:02

一个区间,设其为 [l,r][l,r],然后每两个数有一个值是 f(a,b)f(a,b),然后求其前 kk 大

我的思路:

令二元组集合为 SS,每次用线段树求出这个区间的 max⁡{f(i,j)}\max\{f(i,j)\},然后将 (i,j)(i,j) 从 SS 中删除,继续求其 maxmax

这里的问题是,怎么将 i,ji,j 删掉,老师说有个经典套路是拆区间,但是我不理解为什么

就是 [l,r][l,r] 中有两个点 i,ji,j 且 i<ji< j,然后拆出很多个区间可以类似于把 (i,j)(i,j) 从 SS 中删去

哪位大佬会,请讲清楚点,谢谢,可以给个关注

2023/10/1 09:02
加载中...