Truy vấn max

Điểm: 4,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Nguồn bài:

https://lqdoj.edu.vn/problem/lmhquery

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Java, Javascript, Kotlin, Pascal, Python, Scratch

Hệ thống quản lý điểm số của trường LTV cần quản lý thông tin điểm số của $n$ bạn học sinh được đánh số từ $1$ đến $n$ . Điểm số bắt đầu của tất cả các bạn là $0$ và hệ thống sẽ cung cấp hai lệnh:

Lệnh cập nhật $S (j, k)$ : Đặt điểm số của học sinh thứ $j$ là $k$ ( $1 \leq j \leq n - 1$ ; $1 \leq k \leq 10^{9} - 1$ ).
Lệnh truy vấn $Q (i, j)$ : Cho biết điểm số cao nhất của các học sinh có thứ tự từ $i$ đến $j$ ( $1 \leq i \leq j \leq n$ ).

Yêu cầu: Cho một dãy $m$ lệnh thuộc một trong hai lệnh trên, hãy trả lời tất cả câu hỏi truy vấn.

Dữ liệu vào

Dòng $1$ chứa hai số nguyên dương $n, m$ ( $n, m \leq 100 000$ ).
m dòng tiếp theo, mỗi dòng chứa thông tin về một lệnh, đầu tiên là một ký tự thuộc tập {S,Q}.
- Nếu ký tự đầu dòng là $S$ , tiếp theo là hai số nguyên $j, k$ cho biết đó là lệnh $S (j, k)$ .
- Nếu ký tự đầu dòng là $Q$ , tiếp theo là hai số nguyên $i, j$ cho biết đó là lệnh $Q (i, j)$ .

Dữ liệu ra

Tương ứng với mỗi lệnh truy vấn $Q$ trong input, ghi ra trên một dòng một số nguyên là câu trả lời cho truy vấn đó.

Ví dụ

Input	Output	Giải thích
5 6 S 2 1 S 4 5 Q 2 4 S 3 6 S 2 7 Q 1 4	5 7	Sau $S (2, 1)$ và $S (4, 5)$ : dãy điểm là $[0, 1, 0, 5, 0]$ . Truy vấn $Q (2, 4)$ : max của $[1, 0, 5] = 5$ . Sau $S (3, 6)$ và $S (2, 7)$ : dãy điểm là $[0, 7, 6, 5, 0]$ . Truy vấn $Q (1, 4)$ : max của $[0, 7, 6, 5] = 7$ .

Bình luận

Không có bình luận tại thời điểm này.