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

题目链接

题意:

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

思路:

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

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

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

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

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

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

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

 

 

 

bzoj 1901: Zju2112 Dynamic Rankings (可持久化线段树,区间动态第k大)

Description

给定一个含有n个数的序列a[1],a[2],a[3]……a[n],程序必须回答这样的询问:对于给定的i,j,k,在a[i],a[i+1
],a[i+2]……a[j]中第k小的数是多少(1≤k≤j-i+1),并且,你可以改变一些a[i]的值,改变后,程序还能针对改
变后的a继续回答上面的问题。

Input

第一行有两个正整数n(1≤n≤10000),m(1≤m≤10000)。
分别表示序列的长度和指令的个数。
第二行有n个数,表示a[1],a[2]……a[n],这些数都小于10^9。
接下来的m行描述每条指令
每行的格式是下面两种格式中的一种。
Q i j k 或者 C i t
Q i j k (i,j,k是数字,1≤i≤j≤n, 1≤k≤j-i+1)
表示询问指令,询问a[i],a[i+1]……a[j]中第k小的数。
C i t (1≤i≤n,0≤t≤10^9)表示把a[i]改变成为t
m,n≤10000

Output

 对于每一次询问,你都需要输出他的答案,每一个输出占单独的一行。

Sample Input

5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3

Sample Output

3
6

思路:

现在我们已经会了用可持久化线段树,去做静态区间第k大的问题。

考虑一次修改,修改的元素会影响后面所有建好的线段树,时间代价是无法承受的。

我们考虑root[i]表示的这颗线段树,它保存的是从第一个元素开始插入到第i个元素后的数字区间。也就是说每次我们进行线段树区间相减时,我们是对两个前缀和[1, l – 1]和[1, r]进行了相减。

所以我们需要的是,以一个可以接受的时间代价,维护一个前缀和。

显然是用BIT来维护。

所以带修改的可持久化线段树,本质上应该是BIT套可持久化线段树。