Median II

View as PDF

Submit solution

Points: 100
Time limit: 5.0s
Memory limit: 940M

Author:
Problem type

Median II

You are given an array a of n elements. Furthermore, there are q queries. Each query is of the form QUERY l r or UPDATE i v. The former is the query from the previous problem, and the letter means to update index i to value v.

Sample Input

5 3
1 2 3 4 5
QUERY 1 4
UPDATE 2 10
QUERY 1 4

Sample Output

3
4

Constraints

1 \le n,q \le 1e5 1 \le a[i] \le 1e4


Comments

There are no comments at the moment.