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
ko quá khó
tốn 1 hit để sửa int thành long long, tức thế cơ chứ lị
tham + lazy update là đc , code khá ngắn
nếu áp dụng loại qhđ này vào mảng 2 chiều thì sao nhờ 🤔
Em nghĩ bài này độ khó không tới mức 400