odd doctor 已更新

CRB and Queries

Time Limit
6s
Memory Limit
131072KB
Judge Program
Standard
Ratio(Solve/Submit)
100.00%(1/1)
Description:

There are N boys in CodeLand.
Boy i has his coding skill Ai.
CRB wants to know who has the suitable coding skill.
So you should treat the following two types of queries.
Query 1: 1 l v
The coding skill of Boy l has changed to v.
Query 2: 2 l r k
This is a report query which asks the k-th smallest value of coding skill between Boy l and Boy r(both inclusive).

Input:

There are multiple test cases. 
The first line contains a single integer N.
Next line contains N space separated integers A1A2, …, AN, where Ai denotes initial coding skill of Boy i.
Next line contains a single integer Q representing the number of queries.
Next Q lines contain queries which can be any of the two types.
1 ≤ NQ ≤ 105
1 ≤ Aiv ≤ 109
1 ≤ l ≤ r ≤ N
1 ≤ k ≤ r – l + 1

Output:

For each query of type 2, output a single integer corresponding to the answer in a single line.

Sample Input:
5
1 2 3 4 5
3
2 2 4 2
1 3 6
2 2 4 2
Sample Output:
3
4
Source:

2015 Multi-University Training Contest 10


Submit