Truy cập lịch sử


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 1G

Problem type

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

There are no comments at the moment.