Query-Max 2

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
hhoangcpascal
Dạng bài
Điểm: 450 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho dãy \(a\) gồm \(n\) phần tử là các số nguyên dương \(a_{1}, a_{2}, \ldots, a_{N}\). Cho \(q\) thao tác thực liện lần lượt, thao tác thứ \(i\) sẽ có một trong hai loại như sau:

  • \(1\) \(p\) \(x\): Chèn giá trị \(x\) vào giữa hai vị trí \(p - 1\) và \(p\) trong dãy \(a\) \((1 \leq p \leq t + 1\), với \(t\) là số phần tử hiện có trong dãy \(a\). Nếu \(p = t + 1\), chèn \(x\) vào cuối dãy \(a\).
  • \(2\) \(u\) \(v\): Tìm giá trị lớn nhất trong các phần tử từ vị trí \(u\) tới vị trí \(v\) \((1 \leq u \leq v \leq t\), với \(t\) là số phần tử hiện có trong dãy \(a).\)

Yêu cầu: Thực hiện tất cả lần lượt \(Q\) thao tác, và in ra kết quả của thao tác loại \(2\).

Input

  • Dòng thứ nhất gồm hai số nguyên dương \(n, q\) \((1 \leq n, q \leq 10^{5})\).
  • Dòng thứ hai gồm \(N\) số nguyên dương \(a_{1}, a_{2}, \ldots, a_{N}\) \((a_{i} \leq 10^{9})\).
  • \(q\) dòng tiếp theo, mỗi dòng thể hiện 1 truy vấn thuộc 1 trong 2 loại:/
    • \(1\) \(p\) \(x\) \((1 \leq p \leq n, 1 \leq x \leq 10^{9})\).
    • \(2\) \(u\) và \(v\) \((1 \leq u \leq v \leq n)\).

Output

  • Với thao tác loại \(2\) có dạng \(2\) \(u\) \(v\), in ra giá trị lớn nhất trong các phần tử từ vị trí \(u\) tới vị trí \(v\)

Scoring

  • Subtask \(1\) (\(30\%\) số điểm): \(n, q \leq 10^{3}\).
  • Subtask \(2\) (\(30\%\) số điểm): các thao tác \(1\) luôn được thực hiện trước các thao tác \(2\).
  • Subtask \(3\) (\(40\%\) số điểm): không có rằng buộc gì thêm.

Example

Test 1

Input 
3 4
2 3 1
1 3 2
2 2 3
1 3 5
2 1 4
Output 
3
5

Bình luận