[Algorytmy] Liczba podciągów, każde kolejne liczby różne
: 10 wrz 2015, o 22:36
Witam,
Dany jest ciąg liczb, znaleźć liczbę podciągów takich, że każde dwa sąsiednie elementy są różne.
Podciągi nie muszą być spójne.
No to znowu, mamy drzewo AVL. Przechowujemy pary:
\(\displaystyle{ (x, y, z)}\) gdzie \(\displaystyle{ x}\) to element, zaś \(\displaystyle{ y}\) oznacza liczbę podciągów zakończonych w tym elemencie. \(\displaystyle{ z}\) to suma drugiej współrzędnej w całym poddrzewie.
Gdy wstawiamy element, który już jest w drzewie, to nie dodajemy nowego węzła, ale aktualizujemy (
druga współrzędna się podwaja, zaś trzecią
Lecimy liniowo po całym ciągu. Załóżmy, że analizujemy \(\displaystyle{ a_i}\). Korzystając z drzewa zliczamy wszystkie (trzecia współrzędna) podciągi kończące się na mniejszej liczbie. Następnie kończące się na większej liczbie niż \(\displaystyle{ a_i}\). Sumujemy, wychodzi \(\displaystyle{ t}\). Dalej już dodajemy do drzewa \(\displaystyle{ (a_i, t+1, t+1)}\) i aktualizujemy w górę drzewa trzecią współrzędną.
Całość liniowo-log. Ok ?
Dany jest ciąg liczb, znaleźć liczbę podciągów takich, że każde dwa sąsiednie elementy są różne.
Podciągi nie muszą być spójne.
No to znowu, mamy drzewo AVL. Przechowujemy pary:
\(\displaystyle{ (x, y, z)}\) gdzie \(\displaystyle{ x}\) to element, zaś \(\displaystyle{ y}\) oznacza liczbę podciągów zakończonych w tym elemencie. \(\displaystyle{ z}\) to suma drugiej współrzędnej w całym poddrzewie.
Gdy wstawiamy element, który już jest w drzewie, to nie dodajemy nowego węzła, ale aktualizujemy (
druga współrzędna się podwaja, zaś trzecią
Lecimy liniowo po całym ciągu. Załóżmy, że analizujemy \(\displaystyle{ a_i}\). Korzystając z drzewa zliczamy wszystkie (trzecia współrzędna) podciągi kończące się na mniejszej liczbie. Następnie kończące się na większej liczbie niż \(\displaystyle{ a_i}\). Sumujemy, wychodzi \(\displaystyle{ t}\). Dalej już dodajemy do drzewa \(\displaystyle{ (a_i, t+1, t+1)}\) i aktualizujemy w górę drzewa trzecią współrzędną.
Całość liniowo-log. Ok ?