DMOPC '19 Contest 2 P3 - Selection

View as PDF

Submit solution


Points: 12
Time limit: 1.4s
Python 4.5s
Memory limit: 256M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Veshy has a box with N items, the ith of which has a "goodness" of g_i on Veshy's standards. Over a period of M minutes, one of two events may occur. On the ith minute, either Veshy's standards have changed and the a_ith item's "goodness" has changed to b_i, or he wants to know the goodness of the c_ith best item in the subarray of items, g_{l_i},g_{l_i+1},\ldots,g_{r_i}.

It is recommended Python users use PYPY instead.

Constraints

In all subtasks,
1 \le N \le 300\,000
1 \le M \le 100\,000
0 \le g_i,b_i \le 20
1 \le a_i,l_i,r_i,c_i \le N

Subtask 1 [10%]

N\le100

Subtask 2 [30%]

0\le g_i,b_i\le 1

Subtask 3 [60%]

No additional constraints

Input Specification

The first line contains two space-separated integers, N and M.
The next line contains N integers, the ith of which being g_i.
M lines follow, each of which are either in the form:
1 a b - the a_ith item now has goodness b_i
2 l r c - Veshy wants to know the goodness c_ith best item in the subarray of items: l,l+1,\ldots,r

Output Specification

For each query, output the goodness of the c_ith best item in the subarray of items. It is guaranteed that there are at least c_i items in the subarray.

Sample Input

5 5
3 15 19 7 14
2 2 4 2
1 2 9
2 1 2 2
1 5 17
2 1 5 3

Sample Output

15
3
9

Comments

There are no comments at the moment.