Tổng truy vấn lớn nhất
Xem PDFCho một mảng gồm \(n\) phần tử và \(q\) truy vấn, mỗi truy vấn được định nghĩa bởi một cặp số nguyên \(l_i,r_i(1\le l_i\le r_i\le n)\) và nhiệm vụ của ta là ứng với mỗi truy vấn, ta cần tìm tổng các phần tử của mảng từ \(l_i\) đến \(r_i\). (bao gồm cả \(l_i,r_i\))
Nhưng có một điều đặc biệt là trước khi thực hiện \(q\) truy vấn này, ta cần phải sắp xếp lại mảng theo thứ tự nào đó sao cho tổng tất cả các kết quả của \(q\) truy vấn nhận được là lớn nhất có thể, và tổng kết quả lớn nhất đó chính là kết quả cần tìm.
Input
-
Dòng thứ nhất chứa hai số nguyên \(n,q(1\le n\le 200000,1\le q\le 200000)\)
-
\(q\) dòng tiếp theo, mỗi dòng chứa cặp số nguyên \(l_i,r_i(1\le l_i\le r_i\le n)\)
Output
- In ra giá trị cần tìm
Example
Test 1
Input
5 3
3 2 1 5 4
1 2
1 3
2 3Output
29Note
Đầu tiên ta sắp xếp mảng đã cho lại thành: \(3,5,4,1,2\). Khi đó: Ta có tổng lớn nhất cần tìm là: \(8+12+9=29\)
Bình luận
tốn 1 hit để sửa int thành long long, tức thế cơ chứ lị
-
3
nguyenminhhai021009
7:14 p.m. 15 Tháng 1, 2022
-
-2
huyhau6a2
7:15 p.m. 15 Tháng 1, 2022
-
4
nguyenminhhai021009
7:16 p.m. 15 Tháng 1, 2022
-
2
huyhau6a2
7:17 p.m. 15 Tháng 1, 2022
4 bình luận nữabài nào cũng khai long long đi cho khỏe 🙂
thế float cũng khai báo long long à, hmm, rồi cả sàng 10^7 số cũng dùng long long à, ...
thì ý đây đang nói số nguyên sao bạn thích bắt bẻ vậy =)))
thôi đùa đóa thế nha