Jak znaleźć całkowitą liczbę zwiększających się podsekwencji o określonej długości z drzewem indeksu binarnego (BIT)?

Question

Jak znaleźć całkowitą liczbę zwiększających się podsekwencji o określonej długości za pomocą drzewa indeksów binarnych (BIT)?

rzeczywistości to jest problemem z Spoj Online Judge

Przykład
Załóżmy, że ma szereg 1,2,2,10

Rosnące sub-sekwencje o długości 3 są 1,2,4 i 1,3,4

więc, odpowiedź to 2.

Answer 1

Let:

dp[i, j] = number of increasing subsequences of length j that end at i 

Łatwym rozwiązaniem jest w O(n^2 * k):

for i = 1 to n do 
    dp[i, 1] = 1 

for i = 1 to n do 
    for j = 1 to i - 1 do 
    if array[i] > array[j] 
     for p = 2 to k do 
     dp[i, p] += dp[j, p - 1] 

Odpowiedź jest dp[1, k] + dp[2, k] + ... + dp[n, k].

Teraz to działa, ale jest nieefektywne z powodu podanych ograniczeń, ponieważ n może wzrosnąć nawet do 10000. k jest wystarczająco mały, więc powinniśmy spróbować znaleźć sposób na pozbycie się n.

Spróbujmy innego podejścia. Mamy również S - górną granicę wartości w naszej tablicy. Spróbujmy znaleźć algorytm w odniesieniu do tego.

dp[i, j] = same as before 
num[i] = how many subsequences that end with i (element, not index this time) 
     have a certain length 

for i = 1 to n do 
    dp[i, 1] = 1 

for p = 2 to k do // for each length this time 
    num = {0} 

    for i = 2 to n do 
    // note: dp[1, p > 1] = 0 

    // how many that end with the previous element 
    // have length p - 1 
    num[ array[i - 1] ] += dp[i - 1, p - 1] 

    // append the current element to all those smaller than it 
    // that end an increasing subsequence of length p - 1, 
    // creating an increasing subsequence of length p 
    for j = 1 to array[i] - 1 do   
     dp[i, p] += num[j] 

ten ma złożoność O(n * k * S), ale możemy je zmniejszyć do O(n * k * log S) dość łatwo. Potrzebujemy tylko struktury danych, która pozwoli nam efektywnie sumować i aktualizować elementy w zakresie: segment trees, binary indexed trees itd.