[Algorytmy] Liczba podciągów, każde kolejne liczby różne

[matinf]

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 ?

[flashion]

\(\displaystyle{ t}\) - tablica wejściowa
\(\displaystyle{ e}\) - ilość podciągów zakończonych na liczbie i (jeśli liczby są rzędu więcej niż milion, to kompresujemy wcześniej)
\(\displaystyle{ S}\) - suma wszystkich \(\displaystyle{ e}\)

Dla każdego elementu:
- założmy, że \(\displaystyle{ t = x}\),
- aktualizujemy \(\displaystyle{ e[x] = e[x] + (S - e[x]) + 1 = S + 1}\) (dotychczasowa wartość + wszystkie niekończące się na \(\displaystyle{ x}\) i na końcu \(\displaystyle{ x}\) + nowy ciąg 1-elementowy)

\(\displaystyle{ O(n)}\)
Tak na szybko, może być gdzieś tu błąd.

[matinf]

\(\displaystyle{ t}\) - tablica wejściowa
\(\displaystyle{ e}\) - ilość podciągów zakończonych na liczbie i (jeśli liczby są rzędu więcej niż milion, to kompresujemy wcześniej)
\(\displaystyle{ S}\) - suma wszystkich \(\displaystyle{ e}\)

Dla każdego elementu:
- założmy, że \(\displaystyle{ t = x}\),
- aktualizujemy \(\displaystyle{ e[x] = e[x] + (S - e[x]) + 1 = S + 1}\) (dotychczasowa wartość + wszystkie niekończące się na \(\displaystyle{ x}\) i na końcu \(\displaystyle{ x}\) + nowy ciąg 1-elementowy)

\(\displaystyle{ O(n)}\)
Tak na szybko, może być gdzieś tu błąd.

Nie wiem czy to działa, ale tak czy siak nic nie daje. Przyjmujesz za silne założenie. Jak to skompresować ? A co jeśli są też liczby niecałkowite ? Tablica haszująca działa w czasie stałym, ale zamortyzowanym.