Inversion trick

Inizio precisando che ho inventato io questo nome. Per qualche motivo continuo a trovare problemi che si risolvono così quindi tanto vale dargli un nome. Il nome viene dal fatto che ho visto usare questo trucco per la prima volta per contare le inversioni.
Il trucco serve quando preso un array dobbiamo considerare tutti gli elementi $<i$ con valore $>v$. Si può applicare ad esempio se nell transizione della dp devo considerare tutti gli elementi con questa proprietà.

Risorse

• Pdf spiegazione nella sezione 3.6

Problemi

• Paletta
• Lis (longest increasing subsequence) in $N\text{log}N$, su training poldo
• Sandwich