Yet another square root decomposition problem - MarisaOJ: Marisa Online Judge

Given an array

A

$A$ of

n

$n$ integers, there are

q

$q$ queries, each falling into one of two types: -

1 l r x y

$1 l r x y$ : For all

l \leq i \leq r

$l \le i \le r$ where

A_{i} = x

$A_i = x$ , replace

A_{i}

$A_i$ with

y

$y$ . -

2 l r k

$2 l r k$ : Find the

k

$k$ -th smallest value in the range

A_{l}, A_{l + 1}, . . ., A_{r}

$A_l, A_{l+1}, ..., A_r$ . ### Input - The first line contains two integers

n, q

$n, q$ . - The second line contains

n

$n$ integers

A_{i}

$A_i$ . - The next

q

$q$ lines each contain a query in the specified format. ### Output - Print an integer as the answer for each query of type

2

$2$ . ### Constraints -

1 \leq n, q, A_{i}, x, y \leq 10^{5}

$1 \le n, q, A_i, x, y \le 10^5$ . -

1 \leq l \leq r \leq n

$1 \le l \le r \le n$ . ### Example Input:

99145523122145112111299129912782189232473267113643

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

Output:

122231

$1 2 2 2 3 1$

Square root decomposition
	Frequency
	Tree query
	Inversions query
	Nearest vertex
	Dominating color
	String occurences 3
	Inversions query 2
	Pair
	Sparse update
	Tree
	Range query
	String concatenation
	Subarray distance
	Chameleon
	Knapsack
	Bit counting
	Subsequence queries
	Sub-subsequence
	Delete numbers
	Mode
	Marisa is happy
	Inversions query 3
	Upperbound
	23 path
	Yet another square root decomposition problem
	Marisa plays poker
	Wonderful world

Topic

Data structure

Rating

2400

Source

Ynoi

Solution (1)

Solution