Lời giải đầy đủ tại đây. Slides chữa bài của VNOI tại đây.

Tóm tắt đề bài

Cho ~N~ loại quà, trong đó loại quà thứ ~i~ có ~S_i~ món với khối lượng mỗi món là ~W_i~. Ông già Noel có ý định tạo ra các túi quà để tặng cho các bạn nhỏ, mỗi túi quà phải có đúng ~K~ món quà sao cho không có hai món quà nào thuộc cùng một loại.

Bạn đóng vai trợ lý phải trả lời ~Q~ câu hỏi của ông già Noel, với mỗi câu hỏi thuộc một trong hai loại như sau:

• Loại 1 ~(1\ M\ K\ T)~: Kiểm tra xem có thể tạo ra ~T~ túi quà sao cho tổng khối lượng của tất cả món quà được chọn không vượt quá ~M~ hay không.
• Loại 2 ~(2\ M\ K)~: Xác định số lượng túi quà tối đa có thể tạo được sao cho tổng khối lượng của tất cả món quà được chọn không vượt quá ~M~.

Giới hạn và subtask

• ~1\le N,Q\le 10^5~
• ~1\le W_i\le 10^5~ với mọi ~i~ từ ~1~ đến ~N~
• ~1\le S_i\le 10^5~ với mọi ~i~ từ ~1~ đến ~N~
• ~1\le M,K,T\le 10^9~ với mọi câu hỏi loại 1
• ~1\le M,K\le 10^9~ với mọi câu hỏi loại 2

Subtask 1: ~S_i=1~ với mọi ~i~ từ ~1~ đến ~N~

Trong subtask này, mỗi loại quà chỉ có một món quà nên ta không cần phải quan tâm điều kiện thứ hai của việc chọn túi quà (không được có hai món quà nào cùng loại quà).

Xét câu hỏi loại 1, ta áp dụng tham lam bằng cách sắp xếp lại các món quà theo khối lượng tăng dần. Với mỗi túi quà, ta ưu tiên chọn các món quà có khối lượng bé nhất.

Như vậy ta có thể thấy:

• Trong lần chọn đầu tiên, hiển nhiên ta sẽ lấy ~K~ món quà bé nhất để bỏ vào túi thứ nhất.
• Trong lần chọn thứ hai, ta lấy các món quà bé thứ ~K+1,K+2,\dots,2K~ để bỏ vào túi thứ hai.
• Cứ tiếp tục như vậy, trong lần chọn thứ ~T~, ta lấy các món quà có khối lượng bé thứ ~(T-1)\times K+1,(T-1)\times K+2,\dots,T\times K~ bỏ vào túi thứ ~T~.

Điều này tương đương rằng với câu hỏi loại 1, phương án tối ưu sẽ là chọn ra ~K\times T~ món quà có khối lượng bé nhất để lấy tổng và kiểm tra.

Lưu ý: Cần phải kiểm tra điều kiện ~K\times T\le N~ để đảm bảo việc lấy quà là hợp lệ.

Để giải quyết câu hỏi loại 1 nhanh, ta có thể áp dụng mảng tổng dồn (prefix sum).

Xét câu hỏi loại 2, ta có thể giải quyết bằng chặt nhị phân. Khi xét đến một giá trị ~mid~ trong quá trình chặt, điều kiện kiểm tra lại đưa về một câu hỏi loại 1.

Độ phức tạp: ~O\left((N+Q)\times log(N)\right)~.

Subtask 2: ~N,Q\le 1000~ và chỉ có câu hỏi loại 1

Từ subtask này, mỗi loại quà có thể có nhiều hơn một món quà nên bài toán đã trở nên phức tạp hơn.

Quay trở lại với câu hỏi loại 1, ta vẫn có thể áp dụng tham lam để thực hiện chọn quà nhằm đạt tổng khối lượng tối thiểu:

• Đầu tiên, ta sắp xếp các loại quà theo khối lượng tăng dần.
• Mỗi lần chọn, ta lấy một món quà từ ~K~ loại quà có khối lượng bé nhất sao cho mỗi loại đều còn ít nhất một món quà có thể dùng.

Từ cách tham lam trên, ta có thể suy ra công thức lấy tổng khối lượng như sau:

• Vì có ~T~ túi kích thước ~K~ nên ta cần chọn ~K\times T~ hộp quà, gọi ~res~ là số lượng hộp còn lại cần lấy.
• Xét từ loại quà có khối lượng bé nhất đến lớn nhất, ta lấy ~min(S,T,res)~ hộp quà từ loại quà đang xét và cộng vào tổng khối lượng, sau đó cập nhật ~res:=res-min(S,T,res)~.

Chứng minh:

• Ta có thể thấy với mỗi loại quà, ta chỉ có thể chọn tối đa ~T~ hộp quà để bỏ vào tối đa ~T~ túi quà khác nhau. Để tối ưu thì rõ ràng với loại quà có khối lượng bé nhất đang xét, ta phải lấy càng nhiều càng tốt.
• Tại sao cách tham lam trên lại đúng và đảm bảo có cách xếp hộp vào các túi? Nếu xếp các hộp quà theo thứ tự lấy từ công thức trên, thì các hộp quà cùng loại sẽ ở nằm trên một đoạn liên tiếp.
• Ta có phương án bỏ quà vào túi như sau: bỏ hộp quà đầu tiên vào túi ~1~, hộp quà thứ hai vào túi ~2~, ..., hộp quà thứ ~T~ vào túi ~T~, hộp quà thứ ~T+1~ vào túi ~1~, hộp quà thứ ~T+2~ vào túi ~2~, ..., hộp quà thứ ~x~ vào túi ~(x-1)\ mod\ T+1~.
• Cách này đảm bảo mỗi túi quà chứa các hộp quà thuộc các loại khác nhau vì với mỗi loại quà, các hộp quà cùng loại chỉ nằm liên tiếp trên một đoạn, và vì không có quá ~T~ hộp quà cùng một loại nên việc hai hộp quà cùng loại chung một túi sẽ không xảy ra.

Với công thức đã chứng minh, ta có thể giải quyết các câu hỏi loại 1 trong ~O(N)~.

Lưu ý: Ta cần phải kiểm tra điều kiện ~res=0~ sau khi áp dụng công thức để đảm bảo tính hợp lệ của việc lấy quà.

Độ phức tạp: ~O\left(Q\times N+N\times log(N)\right)~.

Subtask 3: ~N,Q\le 1000~

Như đã nói ở subtask 1, các câu hỏi loại 2 có thể giải quyết bằng chặt nhị phân.

Độ phức tạp: ~O\left(Q\times N\times log(sum(S))\right)~.

Subtask 4: Chỉ có câu hỏi loại 1

Vì giới hạn lớn, ta không thể giải quyết các câu hỏi loại 1 bằng cày trâu như subtask 2 được nữa.

Giả sử ta đã sắp xếp các loại quà theo khối lượng tăng dần, gọi hai dãy ~F~ và ~G~ có công thức như sau:

$$F_i=F_{i-1}+min(S_i,T)$$

$$G_i=G_{i-1}+W_i\times min(S_i,T)$$

Ta có thể chặt nhị phân vị trí ~x~ lớn nhất sao cho ~F_x\le K\times T~ và tổng sẽ bằng ~G_x+W_{x+1}\times (K\times T-F_x)~. Tuy nhiên, ta cần phải phá điều kiện ~min(S_i,T)~ để có cách giải quyết tốt hơn do mỗi câu hỏi loại 1 lại có giá trị ~T~ khác nhau.

Ta thấy nếu ~S_i\le T~ thì ~min(S_i,T)=S_i~, ngược lại ~min(S_i,T)=T~. Như vậy ta có thể tách phần tính tổng làm hai phần, phần đầu tiên là tổng của ~S_i~ với ~S_i\le T~, phần thứ hai là số giá trị ~S_i>T~ nhân với ~T~.

Ta sẽ xử lý các câu hỏi một cách offline để giải quyết subtask này. Với mảng ~F~, ta tạo hai segment tree/fenwick tree để quản lý tổng và số lượng đã được mô tả ở trên. Mảng ~G~ cũng thực hiện tương tự.

Đầu tiên, ta sắp xếp các câu hỏi theo ~T~ tăng dần. Ban đầu, ta coi ~T=0~ thì tất cả các giá trị ~S_i~ đều lớn hơn ~T~. Khi xét đến câu hỏi có ~T=T'~, ta cập nhật lại các vị trí mới thỏa mãn ~S_i\le T~.

Để có thể làm việc này một cách dễ dàng, ta sắp xếp các chỉ số ~i~ theo ~S_i~ tăng dần. Khi tăng ~T~ lên thì ta chỉ cần cập nhật lại các chỉ số tiếp theo thỏa mãn.

Sau khi cập nhật, ta đã có đủ thông tin để truy vấn các phần tử trên dãy ~F~ và ~G~. Để tìm nhanh chỉ số ~x~ thỏa mãn như đã nói, ta áp dụng walk on segment tree/fenwick tree. Sau đó ta thực hiện truy vấn giá trị của ~G_x~ để xác định tổng khối lượng tối ưu cần tìm.

Các thao tác cập nhật, truy vấn, walk đều có thể thực hiện trong ~O(log(N))~.

Độ phức tạp: ~O\left((N+Q)\times log(N)\right)~.

Subtask 5: Không có ràng buộc gì thêm

Vì tính chất offline của việc giải quyết các câu hỏi loại 1, ta không thể áp dụng chặt nhị phân bình thường được. Thay vào đó, ta sẽ thực hiện chặt nhị phân song song trên tập các câu hỏi loại 2.

Độ phức tạp: ~O\left((N+Q)\times log(N)\times log(sum(S))\right)~.