2016 CCPC 长春 I 题 | hdu 5919 Sequence II (可持久化线段树求区间第k大+可持久化线段树求区间不同数个数)

题目链接

题意:

给定一个序列 n,有 m次查询,每次查询一个区间[l,r],求区间中每一种数在区间中第一次出现的位置的中位数,强制在线。

思路:

先分解一下问题,我们要求一段区间位置的中位数,其实可以分解成,求区间中不同数的个数+求区间中第k大的下标。

对于求区间中不同数的个数,离线可以随便线段树,树状数组,或者莫队也行(观察到数据范围<=2E5)

在线的话,就只能可持久化线段树了。

看到一些题解中说要倒序处理…但是之前写求区间不同数的个数,我都是倒序处理的啊? (回想一下,当时似乎正序处理也行…

倒序处理是为了,处理到第i个的时候,第i个一定是当前后缀区间中,第一个出现的…

然后第二个问题,求区间中第k大的下标,离线做法不少,在线的话,也可以用可持久化线段树求。

所以感觉就是板子题,可持久化线段树的2个应用放在了一起orz

 

 

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz