leftmax

Algoritmul

O selecție e o bucată de elevi pe poziții consecutive $[l, r]$. Condiția privește un singur lucru: cel mai înalt dintre cei aleși trebuie să stea în prima jumătate. Subsecvențe sunt $\sim N^2/2$ — mult prea multe ca să le numeri una câte una la $N = 10^5$.

Trucul e să schimbi perspectiva: în loc să numeri selecții, fixează fiecare elev drept maximul selecției și întreabă-te în câte selecții valide poate fi el cel mai înalt. Un elev de pe poziția $i$ e maximul lui $[l, r]$ exact când în interval nu intră niciun elev mai înalt — deci $l$ stă imediat după cel mai apropiat elev mai înalt din stânga, iar $r$ imediat înainte de cel din dreapta.