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.
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.
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.
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
3 6 3 6
Segment tree? Balanced binary tree? or just store some lists?
Migrated from old NTUJ.
ZJU 2112
| No. | Testdata Range | Score |
|---|