[补题][线段树][权值区间离散化] 2019牛客第七场 E Find the median
本质上是一个离散化的权值线段树，其实很简单，比赛时候没写出来是个遗憾，主要当时没考虑清楚离散化的对象，结果和之后的处理方式。
刚开始看题面里一个数据生成公式，以为是强制在线的，后来发现其实是假的，输入是可以全部离线处理出来的。这样的话就可以先把每一步中的L，R求出来了。之后的话，注意到题目的操作实质上相当于权值线段树的操作就可以计数了，我这里当时以为是add值的操作，其实只是增加了数字的个数而已。但是数字范围会很大，所以要离散化一下。这里要特别注意的是在这种区间的离散化之后，就不是原来线段树了（原来的我们所谓正常的线段树其实相当于是个点树），因此要用[l,r)这种左闭右开的区间来计算，否则二分的时候会漏掉中间的一段[mid,mid+1]。
wa点的话有一个是查询的时候参考值要用long long，因为他最大可能是4e5*1e9的,另一个是要开8倍空间，因为4e5个操作其实有8e5个l(r)值。。。
继续阅读“[补题][线段树][权值区间离散化] 2019牛客第七场 E Find the median”