Editorial for Bedao Grand Contest 10 - NUMBER


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: bedao

Subtask 1

Dễ dàng nhận thấy, số lớn thứ ~k~ trong dãy có giá trị ~a_1 \cdot k~.

Subtask 2

Ta gọi ~minValue~ là giá trị nhỏ nhất của mảng ~a~.

Ta có mảng ~f~ với ~f_i~ ~(0 \leq i < minValue)~ là số có giá trị nhỏ nhất trong dãy ~b~ chia ~minValue~ dư ~i~. Dựng một đồ thị gồm ~minValue~ đỉnh đánh số lần lượt từ ~0, 1, ..., minValue - 1~, nối cạnh ~u~ ~\rightarrow~ ~(u + a_i)~ ~\%~ ~minValue~ trọng số ~a_i~. Vì ~a_1 + a_2 + ...+ a_n \leq 10^6~ ~\Rightarrow~ ~minValue \leq \frac{10^6}{n}~, mỗi đỉnh có tối đa ~n-1~ cạnh nên đồ thị của ta có không quá ~\frac{10^6}{n} \cdot (n-1) \leq 10^6~ cạnh. Giả sử dãy ~b~ có chứa cả giá trị ~0~, ta đặt ~f_0 = 0~ và dùng thuật toán Dijkstra để tính mảng ~f~.

Độ phức tạp: ~O(n \cdot minValue \cdot log2(minValue))~

Từ mảng ~f~, ta suy ra số nhỏ thứ nhì chia ~minValue~ dư ~i~ là ~f_i + minValue~, số nhỏ thứ ba chia minValue dư ~i~ là ~f_i + minValue \cdot 2~, ..., số nhỏ thứ ~x~ chia minValue dư ~i~ là ~f_i + minValue \cdot (x-1)~.

Để tìm số lớn thứ ~k~ của dãy ~b~, ta dùng thuật toán chặt nhị phân các giá trị từ ~1~ đến ~10^{15}~). Để kiểm tra xem đáp án có ~\leq mid~ hay không, ta đếm số lượng giá trị của mảng ~b \leq mid~ bằng cách xét các giá trị ~f_i \leq mid~, lấy tổng ~cnt = \frac{mid}{minValue} - \frac{f_i}{minValue} + (mid \% minValue \geq f_i \% minValue)~. Nếu ~cnt \geq (k+1)~ thì đáp án sẽ ~\leq mid~ (~+1~ do không tính giá trị ~0~).

Độ phức tạp: ~O(q \cdot log2(10^{15}) \cdot minValue)~.

Subtask 3

Ta tính mảng ~f~ tương tự Subtask 2. Vì ~k \leq 5000~ nên ta có thể chuẩn bị trước các giá trị của mảng ~b~ bằng cách dùng cấu trúc dữ liệu priority_queue. Ban đầu ta cho hết tất cả các giá trị ~f_i~ vào trong priority_queue. Tại mỗi lượt, gọi ~cur~ là giá trị nhỏ nhất trong priority_queue hiện tại, ta lấy ~cur~ ra, cho giá trị ~cur~ vào mảng ~b~ và thêm giá trị ~cur + minValue~ vào lại priority_queue.

ĐPT phần này là ~O(5000 \cdot log2(minValue)~.

Subtask 4

Ta tính mảng ~f~ tương tự Subtask 2. Ta sort các giá trị của mảng ~f~ tăng dần và sort các truy vấn tăng dần theo giá trị ~k~. Sử dụng kĩ thuật sweep line để tính đáp án. Ta chia các giá trị ~i~ là dư khi chia cho ~minValue~ vào các nhóm có chỉ số ~\frac{f_i}{minValue}~.

Gọi ~sz_i~ là số lượng giá trị dư thuộc các nhóm có chỉ số ~\leq i~, ~g_i~ là số lượng số thuộc mảng ~b~ có giá trị ~< i \cdot minValue~. Ta có ~g_i~ = ~g_j~ + ~sz_j \cdot (j - i)~ với ~j~ là chỉ số nhóm lớn nhất ~< i~. Ta xác định được chỉ số ~x~ max trong số các nhóm mà ~g_x \leq k~, đặt ~tmp = k - g_x~. Đáp án của câu hỏi số lớn thứ ~k~ trong dãy ~b~ là ~(\frac{tmp}{sz_x} + x) \cdot minValue)~ + giá trị dư lớn thứ ~tmp \% sz_x + 1~ trong số các giá trị dư thuộc nhóm có chỉ số ~\leq x~.

Ta dùng cấu trúc dữ liệu Ordered Set để thuận tiện cho việc tính toán.

Độ phức tạp: ~O((minValue + q) \cdot log2(minValue))~.


Comments

Please read the guidelines before commenting.



  • 0
    nguyenhuunhan   commented on Nov. 1, 2022, 8:41 p.m.

    "Dễ dàng" là dễ thế nào thế ạ? :<