Milk Sum

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Farmer John có $N$ con bò, con bò thứ $k$ có giá trị sản xuất sữa là $a_{k}$ . Mỗi sáng, ông chọn một thứ tự để thả bò ra đồng. Con bò được thả ra thứ $i$ (trong số $N$ con) sẽ đóng góp lượng sữa bằng $i \times a_{k}$ (với $a_{k}$ là giá trị sản xuất sữa của con bò đó).

Tổng lượng sữa $T$ phụ thuộc vào thứ tự thả. Farmer John muốn chọn thứ tự thả để tối đa hóa $T$ .

Cho $Q$ truy vấn. Mỗi truy vấn gồm hai số nguyên $i$ và $j$ , nghĩa là: nếu tạm thời đổi giá trị sản xuất sữa của con bò thứ $i$ thành $j$ , thì tổng lượng sữa tối đa $T$ là bao nhiêu? Các truy vấn độc lập — mỗi truy vấn chỉ thay đổi tạm thời, không ảnh hưởng đến các truy vấn khác.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $N$ .
Dòng thứ hai chứa $N$ số nguyên $a_{1}, a_{2}, \dots, a_{N}$ .
Dòng thứ ba chứa số nguyên $Q$ .
$Q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $i$ và $j$ .

Dữ liệu ra

In $Q$ dòng, mỗi dòng là giá trị $T$ tối đa tương ứng với truy vấn đó.

Ràng buộc

$1 \leq N \leq 1.5 \times 10^{5}$
$0 \leq a_{k} \leq 10^{8}$
$1 \leq Q \leq 1.5 \times 10^{5}$
$1 \leq i \leq N$ , $0 \leq j \leq 10^{8}$

Ví dụ

Input	Output	Giải thích
5 1 10 4 2 6 3 2 1 2 8 4 5	55 81 98	Truy vấn 1: đổi $a_{2} = 10$ thành $1$ , mảng thành $[1, 1, 4, 2, 6]$ . Sắp xếp tăng dần: $[1, 1, 2, 4, 6]$ . $T = 1 \cdot 1 + 2 \cdot 1 + 3 \cdot 2 + 4 \cdot 4 + 5 \cdot 6 = 55$ . Truy vấn 2: đổi $a_{2}$ thành $8$ , mảng $[1, 8, 4, 2, 6]$ , sắp xếp $[1, 2, 4, 6, 8]$ . $T = 1 + 4 + 12 + 24 + 40 = 81$ . Truy vấn 3: đổi $a_{4} = 2$ thành $5$ , mảng $[1, 10, 4, 5, 6]$ , sắp xếp $[1, 4, 5, 6, 10]$ . $T = 1 + 8 + 15 + 24 + 50 = 98$ .

Bình luận

Không có bình luận tại thời điểm này.