Znaleźć liczbę podciągów, w których każde dwie kolejne liczby są różne. Na początku mamy dany ciąg \(\displaystyle{ a_1,...,a_n}\). Podciągi nie muszą być spójne.
Czyli możemy to zrobić tak:
Iterujemy od początku ciągu, rozważamy \(\displaystyle{ a_i}\):
Policz ile podciągów (z żądaną własnością) kończy się na elemencie mniejszym niż \(\displaystyle{ a_i}\).
Zapamiętaj tą informację dla dalszych obliczeń.
W dokładnie ten sam sposób traktujemy elementy większe.
Tak więc pod spodem siedzą dwa drzewa AVL. Pierwsze porównuje operatorem \(\displaystyle{ <}\), drugie zaś \(\displaystyle{ >}\). Kluczem jest wartość elementu w ciągu. Każdy węzeł pamięta dodatkowo ilość podciągów kończącym się na nim mającym żądaną własność (*) oraz sumę z poddrzewa dla wartości (*).
Odpowiedzią jest suma sum z korzeni obu drzew.
Co o tym sądzicie ?