h2(#secv6). 'Secventa 6':problema/secv6

Problema cere determinarea numarului perechilor de indici i, j (i < j) pentru care a{~k~} < a{~i~} si a{~k~} < a{~j~}, unde i < k < j. Sa consideram multimea T a indicilor care verifica relatia de mai sus pentru pozitia p a sirului dat. Daca avem t{~1~} si t{~2~} apartinand lui T, t{~1~} < t{~2~}, cum a{~t1~} < a{~k~} cu t{~1~} < k < p, rezulta ca a{~t2~} < a{~t1~}; asadar multimii ordonate (crescator) T ii corespune o multime ordonate (descrescator) A'. Multimea A' poate fi construita cu ajutorul unei stive sortate, la pasul p sunt scoase din stiva elemente mai mici sau egale decat a{~p~} si este introdus elemntul a{~p~}. Stiva construita astfel contine elementele corespunzatoare indicilor multimii T prezentate mai sus, dar contine si elemente in plus (este respectata numai una din conditiile problemei). Observam ca ultimul element care respecta si a doua conditie este, in ordinea stivei sortate, primul element mai mare sau egal decat a{~p~}. In concluzie numarul de indici care respecta conditia pentru pozitia p este egala cu numarul de elemente scoase din stiva sortata la introducerea elementului a{~p~}; +1 daca ultimul element scos din stiva este diferit de a{~p~}.

Problema cere determinarea numarului perechilor de indici i, j (i < j) pentru care a{~k~} < a{~i~} si a{~k~} < a{~j~}, unde i < k < j. Sa consideram multimea T a indicilor care verifica relatia de mai sus pentru pozitia p a sirului dat. Daca avem t{~1~} si t{~2~} apartinand lui T, t{~1~} < t{~2~}, cum a{~t1~} < a{~k~} cu t{~1~} < k < p, rezulta ca a{~t2~} < a{~t1~}; asadar multimii ordonate (crescator) T ii corespune o multime ordonate (descrescator) A'. Multimea A' poate fi construita cu ajutorul unei stive sortate, la pasul p sunt scoase din stiva elemente mai mici sau egale decat a{~p~} si este introdus elemntul a{~p~}. Stiva construita astfel contine elementele corespunzatoare indicilor multimii T prezentate mai sus, dar contine si elemente in plus (este respectata numai una din conditiile problemei). Observam ca ultimul element care respecta si a doua conditie este, in ordinea stivei sortate, primul element mai mare sau egal decat a{~p~}. In concluzie numarul de indici care respecta conditia pentru pozitia p este egala cu numarul de elemente scoase din stiva sortata la introducerea elementului a{~p~} +1 daca ultimul element scos din stiva este diferit de a{~p~}.