Tối Ưu Tổng Truy Vấn
Xem dạng PDF
Cô bé An rất thích những bài toán liên quan đến truy vấn mảng.
Một ngày nọ, cô gặp một bài toán khá nổi tiếng: bạn có một mảng gồm ~n~ phần tử (các phần tử được đánh số từ ~1~). Ngoài ra, có ~q~ truy vấn; mỗi truy vấn được mô tả bởi một cặp số nguyên ~l_i, r_i~ ~(1 \le l_i \le r_i \le n)~.
Với mỗi truy vấn, bạn cần tìm tổng các phần tử của mảng trong đoạn chỉ số từ ~l_i~ đến ~r_i~ (bao gồm cả hai đầu).
Tuy nhiên, cô bé cảm thấy bài toán này hơi nhàm chán. Cô quyết định thay đổi thứ tự các phần tử trong mảng trước khi trả lời các truy vấn sao cho tổng của tất cả các kết quả truy vấn là lớn nhất có thể.
Nhiệm vụ của bạn là tính giá trị lớn nhất có thể của tổng các kết quả truy vấn sau khi sắp xếp lại mảng một cách tối ưu.
Input
Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~ ~(1 \le n \le 2 \cdot 10^5, \ 1 \le q \le 2 \cdot 10^5)~ — số phần tử của mảng và số truy vấn.
Dòng tiếp theo chứa ~n~ số nguyên ~a_i~ ~(1 \le a_i \le 2 \cdot 10^5)~ — các phần tử của mảng.
Mỗi dòng trong ~q~ dòng tiếp theo chứa hai số nguyên ~l_i, r_i~ ~(1 \le l_i \le r_i \le n)~ — truy vấn thứ ~i~.
Output
In ra một số nguyên duy nhất — tổng lớn nhất có thể của tất cả các truy vấn sau khi sắp xếp lại mảng tối ưu.
Scoring
Sample Input 1
3 3
5 3 2
1 2
2 3
1 3
Sample Output 1
25
Sample Input 2
5 3
5 2 4 1 3
1 5
2 3
2 3
Sample Output 2
33
Notes
Với Test đầu tiên
Ta có thể sắp xếp lại mảng thành ~[2,5,3]~
Khi đó, truy vấn đầu tiên sẽ cho ra kết quả là ~2+5=7~.
Truy vấn thứ hai cho ra kết quả là ~5+3=8~.
Truy vấn thứ ba cho ra kết quả là ~2+5+3=10~.
Kết quả sẽ bằng ~7+8+10=25~.
Có thể chứng minh được là không có phương án nào khác cho ra kết quả lớn hơn.
Bình luận
Unoffical solution:
Bài tương tự ~\to~ 276C - Codeforces