Dọc theo một đường thẳng nằm ngang có \(N\) ngọn núi được đánh số từ \(0\) đến \(N-1\), từ trái qua phải. Chiều cao của ngọn núi \(i\) là \(H_i\) (\(0 \le i \le N-1\)). Có đúng một người sống trên đỉnh của mỗi ngọn núi.

Bạn cần tổ chức \(Q\) cuộc họp được đánh số từ \(0\) đến \(Q-1\). Tham gia cuộc họp \(j\) (\(0 \le j \le Q-1\)) sẽ là tất cả những người sống trên đỉnh các ngọn núi từ \(L_j\) đến \(R_j\), kể cả hai đầu mút (\(0 \le L_j \le R_j \le N-1\)). Đối với cuộc họp này, bạn cần chọn ngọn núi \(x\) làm nơi diễn ra cuộc họp (\(L_j \le x \le R_j\)). Chi phí của cuộc họp phụ thuộc vào lựa chọn của bạn và được tính như sau:

• Chi phí của thành viên đến từ ngọn núi \(y\) (\(L_j \le y \le R_j\)) là độ cao lớn nhất của các ngọn núi trong khoảng giữa hai ngọn núi \(x\) và \(y\), kể cả hai đầu mút. Đặc biệt, chi phí của thành viên đến từ ngọn núi \(x\) là \(H_x\), tức chiều cao của ngọn núi \(x\).
• Chi phí của cuộc họp là tổng các chi phí của tất cả các thành viên.

Đối với mỗi cuộc họp, bạn phải tìm chi phí nhỏ nhất có thể để tổ chức nó.

Chú ý là tất cả các thành viên sẽ quay lại ngọn núi của mình sau mỗi cuộc họp, do đó chi phí của một cuộc họp không bị ảnh hưởng bởi các cuộc họp trước đó.

Chi tiết cài đặt

Bạn cần cài đặt hàm sau, với chữ ký C++ trong tệp meetings.h của gói đính kèm:

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R);

• H: mảng độ dài \(N\), biểu diễn chiều cao của các ngọn núi.
• L và R: các mảng độ dài \(Q\), biểu diễn các khoảng ngọn núi có người tham gia các cuộc họp.
• Hàm này cần trả lại mảng \(C\) độ dài \(Q\), gồm các số nguyên \(64\) bit. Giá trị của \(C_j\) (\(0 \le j \le Q-1\)) phải là chi phí nhỏ nhất có thể để tổ chức cuộc họp \(j\).
• Chú ý là các giá trị \(N\) và \(Q\) là độ dài của các mảng, và có thể lấy được theo cách mô tả trong Lưu ý cài đặt.

Ví dụ

Giả sử \(N=4\), \(H=[2,4,3,5]\), \(Q=2\), \(L=[0,1]\) và \(R=[2,3]\).

Trình chấm gọi minimum_costs([2, 4, 3, 5], [0, 1], [2, 3]).

Cuộc họp \(j=0\) có \(L_j=0\) và \(R_j=2\), vì thế những người sống ở các ngọn núi \(0\), \(1\) và \(2\) sẽ tham gia. Nếu ngọn núi \(0\) được chọn làm nơi tổ chức cuộc họp thì chi phí của cuộc họp \(0\) được tính như sau:

• Chi phí của thành viên đến từ ngọn núi \(0\) là \(\max\{H_0\}=2\).
• Chi phí của thành viên đến từ ngọn núi \(1\) là \(\max\{H_0,H_1\}=4\).
• Chi phí của thành viên đến từ ngọn núi \(2\) là \(\max\{H_0,H_1,H_2\}=4\).
• Vì vậy, chi phí của cuộc họp \(0\) là \(2+4+4=10\).

Không thể tổ chức cuộc họp \(0\) với chi phí nhỏ hơn, do đó chi phí nhỏ nhất để tổ chức cuộc họp \(0\) là \(10\).

Cuộc họp \(j=1\) có \(L_j=1\) và \(R_j=3\), vì thế những người sống ở các ngọn núi \(1\), \(2\) và \(3\) sẽ tham gia. Nếu ngọn núi \(2\) được chọn làm nơi tổ chức cuộc họp thì chi phí của cuộc họp \(1\) được tính như sau:

• Chi phí của thành viên đến từ ngọn núi \(1\) là \(\max\{H_1,H_2\}=4\).
• Chi phí của thành viên đến từ ngọn núi \(2\) là \(\max\{H_2\}=3\).
• Chi phí của thành viên đến từ ngọn núi \(3\) là \(\max\{H_2,H_3\}=5\).
• Vì vậy, chi phí của cuộc họp \(1\) là \(4+3+5=12\).

Không thể tổ chức cuộc họp \(1\) với chi phí nhỏ hơn, do đó chi phí nhỏ nhất để tổ chức cuộc họp \(1\) là \(12\).

Các tệp sample-01-in.txt và sample-01-out.txt trong gói nén zip đính kèm tương ứng với ví dụ này. Các ví dụ về dữ liệu vào/ra khác cũng có trong gói đính kèm.

Hạn chế

• \(1 \le N \le 750\,000\).
• \(1 \le Q \le 750\,000\).
• \(1 \le H_i \le 1\,000\,000\,000\) (\(0 \le i \le N-1\)).
• \(0 \le L_j \le R_j \le N-1\) (\(0 \le j \le Q-1\)).
• \((L_j,R_j) \ne (L_k,R_k)\) (\(0 \le j < k \le Q-1\)).

Phân nhóm

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu vào theo khuôn dạng sau:

• Dòng \(1\): \(N\ Q\).
• Dòng \(2\): \(H_0\ H_1\ \ldots\ H_{N-1}\).
• Dòng \(3+j\) (\(0 \le j \le Q-1\)): \(L_j\ R_j\).

Trình chấm mẫu in giá trị trả lại bởi minimum_costs theo khuôn dạng sau:

• Dòng \(1+j\) (\(0 \le j \le Q-1\)): \(C_j\).

Dữ liệu vào của ví dụ trên:

4 2
2 4 3 5
0 2
1 3

Dữ liệu ra tương ứng:

10
12