Hướng dẫn giải của Trò chơi vòng kẹo
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Tác giả:
Để làm được bài này, bạn cần biết kĩ thuật mảng hiệu:
Gọi $d[i]$ là hiệu của ~a[i] - a[i-1]~.
Vậy ~a[i] = d[1] + d[2] + \cdots + d[i]~
Với mỗi truy vấn, có ~2~ trường hợp:
- ~l \le r~: Thao tác của mảng hiệu bình thường, ~d[l] += 1~, ~d[r+1] -= 1~.
- ~r < l~: Do đoạn cần cập nhật có thể xoay vòng, nên thao tác này có thể tách thành ~2~ thao tác là tăng đoạn ~l~ đến ~n~, và đoạn từ ~1~ đến ~r~
Sau khi có được mảng ~d~, ta chỉ cần cộng dồn lại để được mảng ~a~ và lấy số max và in ra.
Bình luận