Truy vấn giá trị nhỏ nhất động (Dynamic Range Minimum Queries)

Nguồn: CSES

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho một mảng gồm $n$ số nguyên. Có $q$ thao tác. Mỗi thao tác hoặc gán một giá trị mới cho một vị trí, hoặc yêu cầu tìm giá trị nhỏ nhất trên một đoạn liên tiếp của mảng.

Input

• Dòng đầu chứa hai số nguyên $n$ và $q$.
• Dòng thứ hai chứa $n$ số nguyên $x_1,x_2,\ldots,x_n$.
• Mỗi trong $q$ dòng tiếp theo có dạng 1 k u để gán $x_k=u$, hoặc 2 a b để hỏi giá trị nhỏ nhất trong $x_a,x_{a+1},\ldots,x_b$.

Output

Với mỗi thao tác loại 2, in giá trị nhỏ nhất của đoạn được yêu cầu trên một dòng.

Subtask

• Subtask 1 — 20%: $1 \le n,q \le 1000$, $1 \le x_i,u \le 10^6$.
• Subtask 2 — 30%: $1 \le n,q \le 50000$, $1 \le x_i,u \le 10^9$.
• Subtask 3 — 50%: $1 \le n,q \le 2\cdot10^5$, $1 \le x_i,u \le 10^9$.

Ví dụ

Input

8 4
3 2 4 5 1 1 5 3
2 1 4
2 5 6
1 2 3
2 1 4

Output

2
1
3

Giải thích

Ban đầu, giá trị nhỏ nhất trên $[1,4]$ là $2$, còn trên $[5,6]$ là $1$. Sau thao tác 1 2 3, đoạn $[1,4]$ trở thành $3,3,4,5$, vì vậy giá trị nhỏ nhất là $3$.