Apple trees 4 - MarisaOJ: Marisa Online Judge

Marisa planted

n

$n$ apple trees in a row. Each tree, denoted as the

i^{t h}

$i^{th}$ tree, can initially grow apples of size

A_{i}

$A_i$ . However, due to the rain, some trees mutate, resulting in changes to the sizes of their apples. There are

q

$q$ event that happen chronological order: -

1 i x

$1 i x$ : apples on tree

i

$i$ change their size to

x

$x$ . -

2 l r k

$2 l r k$ : For her research purposes, Marisa conducts a query in the form of

(l, r, k)

$(l, r, k)$ .She needs to find the

k^{t h}

$k^{th}$ smallest apple size among the trees in the range

[l, r]

$[l, r]$ . Please help her answering these queries. ### Input - The first line contains two integers

n, q

$n,q$ . - The second line contains

n

$n$ integer

A_{i}

$A_i$ . - The next

q

$q$ lines, each line contains a query in the aforementioned format. ### Output - Print an integer, which represents the answer for each query of type 2. ### Constraints -

1 \leq n, q \leq 10^{5}

$1 \le n,q \le 10^5$ -

1 \leq A_{i} \leq 10^{9}

$1 \le A_i \le 10^9$ . -

1 \leq l \leq r \leq n

$1 \le l \le r \le n$ . -

1 \leq k \leq r - l + 1

$1 \le k \le r - l + 1$ . -

1 \leq i \leq n

$1 \le i \le n$ . -

1 \leq x \leq 10^{9}

$1 \le x \le 10^9$ . ### Example Input:

533721821311222243

$5 3 3 7 2 1 8 2 1 3 1 1 2 2 2 2 4 3$

Output:

22

$2 2$

Parallel binary search
	Apple trees
	Apple trees 2
	Apple trees 3
	Apple trees 4

Topic

Binary search

Data structure

Rating

2200

Solution (0)

Solution