Truy cập lịch sử
Cho dãy $a_1,a_2,...,a_N$ và $Q$ truy vấn. Mỗi truy vấn thuộc 1 trong 2 loại sau:
1 i k: Cập nhật $a_i \leftarrow k$.2 x y p: Tính giá trị lớn nhất của $a_x, ..., a_y$ với dãy $a$ là phiên bản sau thao tác cập nhật (loại 1) thứ $p$. Xem dãy $a$ ban đầu là phiên bản sau thao tác cập nhật thứ 0.
Dữ liệu
- Dòng đầu tiên chứa 2 số nguyên $N, Q \ (1\le N, Q \le 10^5)$;
- Dòng tiếp theo chứa $N$ số nguyên $a_i \ (1\le a_i \le 10^9)$;
- $Q$ dòng tiếp theo, mỗi dòng chứa một truy vấn theo mẫu trên $(1\le i\le N; 1 \le x \le y \le N; 1\le k \le 10^9; p$ không vượt quá số thứ tự của phiên bản hiện có$)$.
Kết quả
- In kết quả của mỗi truy vấn loại 2 trên mỗi dòng.
Ví dụ
Ví dụ 1
input
5 4
5 4 3 1 2
2 3 5 0
1 3 6
2 1 3 0
2 1 3 1
output
3
5
6
Giải thích
Dãy $a$ có 2 phiên bản:
Phiên bản ban đầu: $[5,4,3,1,2]$.
Phiên bản thứ hai (sau truy vấn thứ 2 - chính là lần cập nhật đầu tiên): $[5,4,6,1,2]$.
Đối với các truy vấn 1, 3, 4, ta có:
Truy vấn 1: Xét phiên bản sau cập nhật thứ 0, tìm max đoạn $a[3..5]$. Kết quả là $max(3,1,2)=3$.
Truy vấn 3: Xét phiên bản sau cập nhật thứ 0, tìm max đoạn $a[1..3]$. Kết quả là $max(5,4,3)=5$.
Truy vấn 4: Xét phiên bản sau cập nhật thứ 1, tìm max đoạn $a[1..3]$. Kết quả là $max(5,4,6)=6$.
Comments