PALETTA SORT-Aiuto?

Aiuto
1

Salve, potreste gentilmente dirmi come si risolve il terzo problema delle oii di quest’anno?
Ho letto in effetti la soluzione, e non è neanche vero che non la ho capita, però alla fine secondo me faccio più confusione io ascrivervi cosa non mi convince nel dettaglio e voi a capirlo che magari a spiegarla da capo. Voglio dire, più o meno ho capito COSA fa, ma non ho capito perchè funziona e ci sono poi un po di passaggi che la codifica e la soluzione a parole mi sembra un po’ diversa.

Ps: so come funziona il fenwick, ne ho implementato uno funzionante che svolge la range sum query e il point update, quindi lo conosco.
Grazie mille in anticipo :slight_smile:

2

L’idea alla base è che una volta ordinato un array ogni elemento sta alla sinistra di tutti gli elementi maggiori o uguali a lui.
Perciò quando vado ad eseguire degli swap verso sinistra tra elementi necessariamente adiacenti ne faccio tanti quanti sono gli elementi più grandi di quello da sistemare.
Difatti gli swap non cambiano l’ordine relativo tra gli elementi che non sto sistemando, perciò una volta che ne ho sistemato uno a sinistra di tutti quelli maggiori o uguali di lui posso tranquillamente passare al prossimo con la sicurezza di non “perdere il posto”.