CSES范围查询部分问题薪资查询问题

Question

我正在尝试解决cses薪资查询(https://cses.fi/problemset/task/1144/)

问题：我会制作一个工资的频率数组，我会使用坐标压缩，但在更新时，我必须重建坐标压缩，这会很混乱。

如何解决这类问题？我在stackoverflow看到了一个博客，但我无法实现隐式分段树的解决方案。

Answer 1

问题的解决方案非常简单。与其只对初始数组进行坐标压缩，不如构建一个新数组，该数组是初始数组和所有更新查询值的并集。请对此执行坐标压缩。你的数组大小最多为N+Q。要执行更新查询，只需找到更新查询值的压缩等效值。