[补题][线段树][权值区间离散化] 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”