TS10 Đồng Tháp 2026 - Cập nhật dãy
Xem dạng PDFTrong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Bình có một mảng gồm ~N~ số nguyên ~a_1, a_2, \dots, a_N~, ban đầu tất cả các phần tử đều bằng ~0~. Cậu ấy thực hiện ~Q~ thao tác trên mảng. Với mỗi thao tác gồm hai số ~l~ và ~r~, Bình sẽ cập nhật các phần tử trong đoạn từ ~l~ đến ~r~ theo dạng "bậc thang".
Cụ thể:
Phần tử ở vị trí ~l~ được cộng thêm ~1~;
Phần tử ở vị trí ~l+1~ được cộng thêm ~2~;
Phần tử ở vị trí ~l+2~ được cộng thêm ~3~;
…
Phần tử ở vị trí ~r~ được cộng thêm ~r-l+1~.
Yêu cầu: Sau khi thực hiện ~Q~ thao tác cập nhật nêu trên, hãy cho biết giá trị lớn nhất trong mảng là bao nhiêu?
Input
Dòng thứ nhất ghi hai số nguyên dương ~N, Q~ ~(1 \le N, Q \le 2 \times 10^5)~.
Trong ~Q~ dòng tiếp theo, dòng thứ ~i~ ghi hai số nguyên ~l_i, r_i~ tương ứng với thao tác cập nhật thứ ~i~ ~(1 \le l_i \le r_i \le N)~. Các số trên cùng một dòng ghi cách nhau một dấu cách.
Output
Một dòng chứa một số nguyên duy nhất là giá trị lớn nhất trong mảng sau ~Q~ thao tác cập nhật.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~60\%~ | ~1 \le N, Q \le 10^3~ |
| 2 | ~40\%~ | ~10^3 < N, Q \le 2 \times 10^5~ |
Sample Input 1
10 3
3 8
2 5
4 9
Sample Output 1
11
Notes
| ~a_1~ | ~a_2~ | ~a_3~ | ~a_4~ | ~a_5~ | ~a_6~ | ~a_7~ | ~a_8~ | ~a_9~ | ~a_{10}~ | |
|---|---|---|---|---|---|---|---|---|---|---|
| Dãy ban đầu | ~0~ | ~0~ | ~0~ | ~0~ | ~0~ | ~0~ | ~0~ | ~0~ | ~0~ | ~0~ |
| Cập nhật lần 1: 3 8 | ~+1~ | ~+2~ | ~+3~ | ~+4~ | ~+5~ | ~+6~ | ||||
| Cập nhật lần 2: 2 5 | ~+1~ | ~+2~ | ~+3~ | ~+4~ | ||||||
| Cập nhật lần 3: 4 9 | ~+1~ | ~+2~ | ~+3~ | ~+4~ | ~+5~ | ~+6~ | ||||
| Dãy sau cập nhật | ~0~ | ~1~ | ~3~ | ~6~ | ~9~ | ~7~ | ~9~ | ~11~ | ~6~ | ~0~ |
Giá trị lớn nhất của dãy sau khi cập nhật là 11.
Bình luận