Tính giá trị tối đa từ [currPos] thành [currPos - k] với mảng lớn

Question

Tôi đang chuẩn bị cho cuộc thi ACM và tôi bị kẹt với vấn đề này.

Bạn có tòa nhà có vị trí nhất định Xi và chiều cao Hi lá chắn được làm bằng thép và họ cần phải được hỗ trợ bởi ít nhất hai tòa nhà có chiều cao tương tự. Đầu bên phải của lá chắn phải nằm trên đỉnh của một số tòa nhà. Tất cả các tòa nhà nằm dưới tấm khiên (bao gồm cả những cái nằm ở cuối) đều được bảo vệ bởi chiếc khiên đó và chiều cao của chúng không thể vượt quá chiều cao mà lá chắn được đặt. Một tòa nhà có thể được bảo vệ với tối đa một lá chắn.

Bạn được cấp số lượng lá chắn vô hạn, mỗi lá có cùng độ dài L. Tìm số lượng tối đa các tòa nhà có thể được bảo vệ bằng khiên và tìm số lượng khiên tối thiểu có thể được sử dụng để bảo vệ số lượng tòa nhà tối đa .

Input

Dòng đầu tiên chứa một số nguyên dương T (1 < = T < = 20), số lượng các trường hợp thử nghiệm.

Mỗi trường hợp thử nghiệm bắt đầu với một dòng có chứa chính xác hai số nguyên: số lượng các tòa nhà N (2 < = N < = 100.000) và chiều dài của một L khiên (1 < = L < = 1000000000). Trong mỗi dòng N tiếp theo có hai số nguyên, Xi (vị trí của tòa nhà thứ i, 0 < = Xi < = 1.000.000.000) và Hi (chiều cao của tòa nhà thứ i, 1 < = Hi < = 1.000.000.000). Các tòa nhà được sắp xếp theo tọa độ x của chúng. Sẽ không có hai tòa nhà có cùng tọa độ x.

Output

Đối với mỗi trường hợp kiểm tra, trên hai đường thẳng, đầu ra số lượng tối đa của các tòa nhà có thể được bảo hiểm và số lượng tối thiểu của lá chắn có thể được sử dụng cho mục đích đó.

Ví dụ

Input 
17 3 
1 2 
2 1 
3 2 
4 3 
5 1 
6 2 
7 4 
8 2 
9 3 
10 4 
11 2 
15 2 
16 1 
17 3 
18 3 
19 1 
20 2 

Output 
11 3 

Explanation: 
first shield: 1,2,3 
second shield: 7,8,9,10 
third shield: 15,16,17,18 

Rõ ràng brute-force giải pháp được dễ dàng mã để mã nhưng sẽ thất bại về thời hạn (1s), tôi đã được đọc về cây phân đoạn, nhưng kể từ khi tôi chưa từng làm việc với phân khúc cây tôi quan tâm là cách để giải quyết vấn đề này hoặc là có một số giải pháp dễ dàng hơn mà tôi đang bỏ lỡ?

PS Mặc dù nó cho biết chiều dài lá chắn là L, nó thực sự là L + 1, tòa nhà cuối cùng phải cao nhất và có tòa nhà ở vị trí [Xi-1, Xi-L] với cùng chiều cao để có thể đặt lá chắn và vị trí xây dựng sẽ được sắp xếp.

Answer 1

Tìm tối đa từ pos - k đến pos còn được gọi là "vấn đề tối đa cửa sổ trượt" và nó có giải pháp O(N) đơn giản mà không có phân đoạn cây hoặc bất kỳ cấu trúc dữ liệu nâng cao nào khác.
Thuật toán như sau:
1) Hãy duy trì deque của các cặp <value, position>.
2) Di chuyển các cửa sổ giới hạn được thực hiện theo cách sau (tôi sử dụng mã giả ở đây):

//Moving the right border. 
right <- right + 1 
cur <- pair<value[right], x[right]> 
while not deque.empty and deque.back.value < cur.value 
    deque.pop_back() 
deque.push_back(cur) 

//Moving the left border. 
left <- left + 1 
while deque.front.position is out of [x[left], x[right]] bounds 
    deque.pop_front() 

3) Tối đa chỉ đơn giản là deque.front.value.

Độ phức tạp của thuật toán này là O(N) vì mỗi phần tử chỉ được đẩy lên deque một lần và nó được loại bỏ chỉ một lần (và mỗi lần lặp lại while vòng lặp trong mã giả ở trên sẽ xóa một phần tử khỏi deque).

Bây giờ là giải pháp cho vấn đề ban đầu về lá chắn:
1) Giả sử dp[pos] = cặp < số lượng tối đa của các tòa nhà được bảo hiểm, số lượng tối thiểu của lá chắn sử dụng > như vậy biên giới đúng tất cả các lá chắn là < = pos.
2) Hãy duy trì hai con trỏ low và high. high là con trỏ đến tòa nhà hiện tại và con trỏ low là con trỏ đến tòa nhà ngoài cùng bên trái sao cho x[high] - x[low] >= L.
3) high con trỏ luôn được tăng thêm một trong vòng lặp for và con trỏ low được điều chỉnh thích hợp (để thỏa mãn thuộc tính 2)).
4) Sau đó dp có thể được tính theo cách sau: cho một giá trị cố định của high, dp[high] là một trong hai dp[high - 1] hoặc dp[low - 1] + high - low + 1 (thứ hai được sử dụng chỉ khi nó có thể đặt một lá chắn từ low để high).
5) Làm thế nào để kiểm tra xem nếu có thể đặt lá chắn? Sử dụng thuật toán tối đa của cửa sổ trượt, có thể duy trì giá trị lớn nhất trong phạm vi [low; high - 1] và kiểm tra xem nó có bằng H[high] hay không.
6) Câu trả lời là dp[N - 1] (với chỉ số dựa trên 0).

Độ phức tạp của giải pháp này là vì low và high luôn được tăng lên và chúng không thể được tăng lên nhiều hơn N lần và độ phức tạp của thuật toán tối đa cửa sổ trượt được hiển thị ở trên.