【zoj2112】Dynamic Rankings

2014年4月20日3,2125

The Company Dynamic Rankings has developed a new kind of computer that is no longer satisfied with the query like to simply find the k-th smallest number of the given N numbers. They have developed a more powerful system such that for N numbers a[1], a[2], …, a[N], you can ask it like: what is the k-th smallest number of a[i], a[i+1], …, a[j]? (For some i<=j, 0<k<=j+1-i that you have given to it). More powerful, you can even change the value of some a[i], and continue to query, all the same.

Your task is to write a program for this computer, which

– Reads N numbers from the input (1 <= N <= 50,000)

– Processes M instructions of the input (1 <= M <= 10,000). These instructions include querying the k-th smallest number of a[i], a[i+1], …, a[j] and change some a[i] to t.

Input

The first line of the input is a single number X (0 < X <= 4), the number of the test cases of the input. Then X blocks each represent a single test case.

The first line of each block contains two integers N and M, representing N numbers and M instruction. It is followed by N lines. The (i+1)-th line represents the number a[i]. Then M lines that is in the following format

Q i j k or
C i t

It represents to query the k-th number of a[i], a[i+1], …, a[j] and change some a[i] to t, respectively. It is guaranteed that at any time of the operation. Any number a[i] is a non-negative integer that is less than 1,000,000,000.

There’re NO breakline between two continuous test cases.

Output

For each querying operation, output one integer to represent the result. (i.e. the k-th smallest number of a[i], a[i+1],…, a[j])

There’re NO breakline between two continuous test cases.

Sample Input

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

Sample Output

3
6
3
6

题解

线段树套平衡树,在线段树的每一个区间内套一棵平衡树

然后二分值判断区间内比它小的数的个数

似乎比可持久更好理解

主要是代码量比较大

treap写的不够顺手

 

  • 黑暗世界2014年4月20日 下午1:53 回复

    系统:正在调用fc函数
    系统:正在对比文件zoj2112from lwher && zoj2112from hzwer
    系统:找不到相异处……

    #1  
    • hzwer2014年4月21日 下午8:51 回复
      admin

      23333

      #11
      • 枫叶红秋雨2015年1月18日 下午11:38 回复

        大神。群里好多人拜摸你!求加群 : 318135341

        #12
  • kd35okc2015年1月18日 上午10:33 回复

    求问root数组在哪里修改过吗?我没看出来。如果没修改,那作用是什么?

    #2  
    • hzwer2015年1月18日 下午1:56 回复
      admin

      insert和del的k是&k

      #21