Bedao Regular Contest 23 - Sân khấu này là của ai?
Xem dạng PDF
Phố Dải Lụa sắp khai mạc "Vũ Điệu Sắc Màu". Dọc phố có ~N~ nhóm nghệ sĩ xếp hàng (~1\leq N \leq 2 \cdot 10^5~), nhóm thứ ~i~ mang mức độ khuấy động là ~A_i~ (~1 \leq A_i \leq 10^9~).
Trong một buổi trình diễn của các nghệ sĩ có chỉ mang mức độ khuấy động là ~B_1, B_2, \cdots, B_{2m}~, đội ngũ của bạn dàn dựng đúng ~m~ tiết mục, mỗi tiết mục bạn sẽ chọn ra hai nghệ sĩ kề nhau, khi đó Điểm Sôi Động (ký hiệu ~S~ của buổi biểu diễn) sẽ tăng lên ~|B_i - B_{i+1}|~ (Với ~1 \leq i < 2m~ là thứ tự của người nghệ sĩ có chỉ số nhỏ hơn). Sau mỗi tiết mục, hai người nghệ sĩ vừa trình diễn sẽ rời sân khấu, để phần còn lại cho những nghệ sĩ còn lại, khoảng trống giữa hai người vừa rời đi sẽ được những người nghệ sĩ ở hai bên dồn lại (vẫn giữ thứ tự).Bạn muốn buổi trình diễn phải tuyệt vời nhất có thể nên tổng ~S~ sau cùng phải là lớn nhất có thể.
Ban tổ chức nhận được ~Q~ yêu cầu trình diễn trên các chặng phố khác nhau (~Q \leq 2 \cdot 10^5~). Mỗi yêu cầu là một đoạn ~[l, r]~ (độ dài chẵn), tức là chỉ đạo đội ngũ bạn dàn dựng tiết mục trên dãy con ~B = A_l, A_{l+1}, \ldots, A_{r}~. Với mỗi yêu cầu, bạn cần cho biết Điểm Sôi Động tối đa bạn có thể đạt được là bao nhiêu.
Input
Dòng đầu gồm hai số nguyên dương ~N~ và ~Q~ tương ứng với số nghệ sĩ hiện tại của bạn và số yêu cầu trình diễn.
Dòng tiếp theo gồm ~N~ số nguyên dương ~A_1, A_2, \ldots, A_{N}~ tương ứng với mức độ khuấy động của các nghệ sĩ.
~Q~ Dòng tiếp theo gồm hai số nguyên dương ~l~ và ~r~ tương ứng với một yêu cầu trình diễn của các nghệ sĩ ~A_l, A_{l + 1}, \ldots, A_r~. (Đảm bảo ~1 \leq l \leq r \leq N~ và ~r - l + 1~ là một số chẵn)
Output
Gồm ~Q~ số nguyên dương, với số thứ ~i~ cho biết Điểm Sôi Động tối đa bạn có thể đạt được nếu sắp xếp các tiết mục tối ưu và hấp dẫn.
Scoring
| Subtask | Điểm | ~N, Q~ |
|---|---|---|
| 1 | ~10\%~ | ~1 \leq N \leq 8, 1 \leq Q \leq 5~ |
| 2 | ~20\%~ | ~1 \leq N \leq 15, 1 \leq Q \leq 10~ |
| 3 | ~30\%~ | ~1 \leq N, Q \leq 2000~ |
| 4 | ~40\%~ | Không có ràng buộc gì thêm |
Sample Input 1
6 2
1 5 4 2 6 7
1 4
1 6
Sample Output 1
6
11
Notes
Trong truy vấn đầu tiên dãy ~B = [1, 5, 4, 2]~ :
Ta chọn tiết mục đầu tiên gồm nghệ sĩ thứ tự ~1~ và ~2~, sau đó dãy ~B = [4, 2]~.
Ta chỉ còn đúng một cách chọn giữa nghệ sĩ thứ tự ~1~ và ~2~ (đã được đánh số lại), sau đó dãy ~B~ rỗng
Như vậy ta nhận được ~S = |1-5| + |4-2| = 6~
Trong truy vấn thứ hai dãy ~B = [1, 5, 4, 2, 6, 7]~
Ta chọn tiết mục đầu tiên gồm nghệ sĩ thứ ~2~ và ~3~, sau đó dãy ~B = [1, 2, 6, 7]~
Ta chọn tiết mục thứ hai gồm nghệ sĩ thứ ~2~ và ~3~ (được đánh số lại), sau đó dãy ~B = [1, 7]~
Ta chỉ còn đúng một cách chọn giữa nghệ sĩ thứ tự ~1~ và ~2~ (đã được đánh số lại), sau đó dãy ~B~ rỗng
Như vậy ta nhận được ~S = |4-5| + |2-6| + |1-7| = 11~
Bình luận
bai nay code Mo sao lai tle the a :(
Với mỗi truy vấn ông bà tổ tiên mách bảo: