Calcolo massimo da [currPos] a [currPos - k] nel grande array

Question

Mi sto preparando per la competizione ACM e sono bloccato con questo problema.

Si sono edifici con data posizione Xi e l'altezza Hi gli scudi sono realizzati in acciaio e hanno bisogno di essere sostenuti da almeno due edifici con la stessa altezza. L'estremità destra dello scudo deve trovarsi in cima ad alcuni edifici. Tutti gli edifici che si trovano sotto lo scudo (compresi quelli che si trovano all'estremità) sono protetti da quello scudo e la loro altezza non può superare l'altezza su cui è posizionato lo scudo. Un edificio può essere protetto con al massimo uno scudo.

Ti viene dato un numero infinito di scudi, ciascuno con la stessa lunghezza L. Trova il numero massimo di edifici che possono essere protetti dagli scudi e trova il numero minimo di scudi che possono essere utilizzati per proteggere il numero massimo di edifici .

ingresso

La prima linea di input contiene un intero positivo T (1 < = T < = 20), il numero di casi di test.

Ogni test inizia con una linea che contiene esattamente due numeri interi: il numero di edifici N (2 < = N < = 100.000) e la lunghezza di uno scudo L (1 < = L < = 1000000000). In ciascuna delle successive righe N ci sono due numeri interi, Xi (la posizione dell'edificio i-esimo, 0 < = Xi < = 1.000.000.000) e Ciao (l'altezza dell'edificio i-esimo, 1 = Ciao < = 1.000.000.000). Gli edifici sono dati ordinati in base alla loro coordinata x. Non ci saranno due edifici con la stessa coordinata x.

uscita

Per ogni test, in due una linea, uscita il numero massimo di edifici che possono essere coperti e il numero minimo di schermi che possono essere utilizzati per questo scopo.

Esempio

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 

Ovviamente la soluzione di forza bruta è facile codice per codice, ma non riuscirà a termine (1s), stavo leggendo su albero segmento, ma dal momento che non hanno funzionato con l'albero del segmento sono interessato è il modo per risolvere questo problema o c'è qualche soluzione più semplice che mi manca?

PS Anche se dice che la lunghezza dello scudo è L, in realtà è L + 1, l'ultimo edificio deve essere il più alto e avere un edificio in posizione [Xi-1, Xi-L] con la stessa altezza per poter posizionare uno scudo e le posizioni degli edifici verranno ordinate.

Answer 1

Trovare il massimo da pos - k a pos è anche noto come "problema massimo finestra scorrevole" e ha una soluzione semplice O(N) senza alberi segmento o qualsiasi altra struttura dati avanzata.
L'algoritmo è il seguente:
1) Manteniamo uno deque di coppie <value, position>.
2) Spostare i limiti della finestra avviene nel modo seguente (io uso pseudo codice qui):

//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) Il massimo è semplicemente deque.front.value.

La complessità di questo algoritmo è O(N) perché ogni elemento viene spostato a deque solo una volta e viene rimosso da essa sola volta (e ogni iterazione del ciclo while in pseudo codice precedente rimuove un elemento dalla deque).

Ora la soluzione al problema originale sugli scudi:
1) Supponiamo dp[pos] = coppia < numero massimo di edifici coperti, il numero minimo di scudi utilizzato > tale che bordo destro tutti gli scudi è < = pos.
2) Manteniamo due indicatori low e high. Il high è un puntatore all'edificio corrente e il puntatore low è un puntatore all'edificio più a sinistra, ad esempio x[high] - x[low] >= L.
3) il puntatore high viene sempre incrementato di uno nel ciclo for e il puntatore low viene regolato in modo appropriato (per soddisfare la proprietà 2)).
4) Poi dp può essere calcolato nel modo seguente: per un valore fisso di high, dp[high] è o dp[high - 1] o dp[low - 1] + high - low + 1 (il secondo viene utilizzato solo se è possibile collocare uno schermo da low a high).
5) Come verificare se è possibile posizionare uno scudo? Utilizzando l'algoritmo massimo della finestra scorrevole, è possibile mantenere il valore massimo nell'intervallo [low; high - 1] e verificare se è uguale a H[high].
6) La risposta è dp[N - 1] (con indicizzazione basata su 0).

La complessità di questa soluzione è O(N) perché low e high sono sempre incrementati e non può essere incrementata oltre N volte e finestra scorrevole massimo algoritmo complessità è stato mostrato sopra.