Obliczanie maks. Z [currPos] na [currPos - k] w dużej tablicy

Question

Przygotowuję się do konkursu ACM i utknąłem z tym problemem.

Masz budynki z danym stanowisku Xi i wysokości Hi tarcze wykonane są ze stali i muszą być obsługiwane przez co najmniej dwa budynki o tej samej wysokości. Prawy koniec tarczy musi znajdować się na szczycie jakiegoś budynku. Wszystkie budynki, które leżą pod tarczą (łącznie z tymi, które leżą na końcu) są chronione przez tę tarczę, a ich wysokość nie może przekraczać wysokości, na której umieszczona jest tarcza. Jeden budynek może być chroniony co najwyżej jedną tarczą.

Otrzymujesz nieskończoną liczbę tarcz o tej samej długości L. Znajdź maksymalną liczbę budynków, które mogą być chronione przez tarcze i znajdź minimalną liczbę osłon, które mogą być użyte do ochrony maksymalnej liczby budynków .

wejściowy

Pierwsza linia wejścia zawiera jedną dodatnią liczbę całkowitą T (1 < < = T = 20), liczby testów.

Każdy przypadek testowy rozpoczyna się od linii, która zawiera dokładnie dwie liczby: liczba budynków N (2 < = N < = 100000) i długość osłony L (L = 1 < < = 1000000000). W każdym z kolejnych N wierszy znajdują się dwie liczby całkowite, Xi (pozycja i-tego budynku, 0 < = Xi < = 1 000 000 000) i Hi (wysokość i-tego budynku, 1 < = Hi < = 1 000 000 000). Budynki są sortowane według współrzędnej x. Nie będzie dwóch budynków o tej samej współrzędnej x.

Wyjście

Dla każdego przypadku testowego, na dwa linia, moc maksymalna liczba budynków, które mogą być objęte, a minimalna liczba osłon, które mogą być wykorzystywane do tego celu.

Przykład

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 

Oczywiście rozwiązanie brute-force jest prosty kod do kodu, ale nie powiedzie się na terminie (1s) czytałem o drzewa segmentu, ale odkąd nie pracował z drzewem segmentu, które mnie interesuje, to sposób na rozwiązanie tego problemu, czy jest jakieś proste rozwiązanie, którego mi brakuje?

PS Chociaż mówi się, że długość osłony wynosi L, to faktycznie L + 1, ostatni budynek musi być najwyższy i mieć budynek na pozycji [Xi-1, Xi-L] o tej samej wysokości, aby móc umieścić osłonę a pozycje budowlane zostaną posortowane.

Answer 1

Określenie maksimum z pos - k na pos jest również znane jako "maksymalny problem z przesuwanym oknem" i ma proste rozwiązanie O(N) bez drzew segmentów lub innych zaawansowanych struktur danych.
Algorytm jest następujący:
1) Załóżmy, że deque par <value, position>.
2) Przesuwanie granic okna odbywa się w następujący sposób (używam pseudo kod tutaj):

//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) maksymalna to po prostu deque.front.value.

złożoności tego algorytmu jest O(N) ponieważ każdy element jest wypychany z deque tylko raz i usuwa się z niego tylko jeden raz (i każdy z while iteracji pętli w pseudokodzie powyżej usuwa jeden element z deque).

Teraz rozwiązanie pierwotnego problemu o tarczach:
1) Załóżmy dp[pos] = para < maksymalna ilość budynków objętych, minimalna liczba tarcze używane > taki sposób, że prawo granica wszystkie ekrany jest < = pos.
2) Załóżmy dwa wskaźniki: low i high. high jest wskaźnikiem do bieżącego budynku, a wskaźnik low jest wskaźnikiem do lewego budynku tak, że x[high] - x[low] >= L.
3) high Wskaźnik jest zawsze zwiększany o jeden w pętli for, a wskaźnik low jest odpowiednio dostosowywany (aby spełnić właściwość 2).
4) Następnie dp może być obliczona w następujący sposób: do stałej wartości high, dp[high] jest albo dp[high - 1] lub dp[low - 1] + high - low + 1 (drugi jest stosowany tylko wtedy, gdy to jest możliwe, aby umieścić tarczę z low do high).
5) Jak sprawdzić, czy możliwe jest umieszczenie tarczy? Wykorzystując algorytm maksymalnego przesuwanego okna, możliwe jest utrzymanie maksymalnej wartości w zakresie [low; high - 1] i sprawdzenie, czy jest ona równa H[high].
6) Odpowiedź brzmi: dp[N - 1] (z indeksacją 0).

złożoność tego rozwiązania jest O(N) ponieważ lowhigh i zawsze zwiększa się i nie może być zwiększana ponad N razy i algorytm okno przesuwne maksymalna złożoność pokazano powyżej.