Potreste darmi un aiuto a capire quale DS usare per risolvere muraglia. Al momento mi vengono varie idee, ma mi sembrano tutte sbagliate.
Grazie
Io l’ho risolto usando BBST (balanced binary search tree)
1 Mi Piace
Prova con un segment tree. Che operazioni deve supportare?
Con un BBST è venuto subito.
1 Mi Piace
Mi potresti dare un piccolo suggerimento per iniziare perché non ho le idee chiare su come utilizzare il BBST per questo problema… grazie…
L’approccio che ho utilizzato io è con segment tree, che a mio parere è una struttura dati molto “riutilizzabile” in quanto molto frequente nei problemi di cp.
Dobbiamo essere in grado di rispondere a 2 tipi di query:
-cambia, che è un point update che facciamo in log(N)
-chiedi, dove invece la situazione si complica leggermente,
considera di salvarti nel segtree il massimo, quello che vuoi andare a fare è le query per trovare il primo e l’ultimo bastione in O(long(N)), che puoi fare con (non so come mettere lo spoiler) una binary search sul segment tree, ovvero fare una ricerca in cui ogni volta ricorri in uno solo dei figli, visitandone al massimo uno per ogni livello → visitando log(N) nodi
Buon lavoro 
e se vuoi ancora qualche hint chiedi pure
3 Mi Piace
Grazie!!!