İkili Dizin Ağacı (BIT) ile belirli bir uzunluğun artırılması alt dizilerinin toplam sayısı nasıl bulunur?

Question

Binary Dizin Ağacı (BIT) ile belirli uzunluktaki Artan alt dizilerin toplam sayısını nasıl bulabilirim?

Aslında bu, ÖrnekSpoj Online Judge

bir sorundur
varsayalım ben bir dizi 1,2,2,10

uzunluğu 3 olan 1,2,4 ve So

1,3,4, cevap artan alt dizileri 2.

Answer 1

Let:

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

Kolay bir çözüm O(n^2 * k) içinde:

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] 

cevap dp[1, k] + dp[2, k] + ... + dp[n, k] olduğunu.

Şimdi, bu çalışma, ancak n10000'a kadar gidebildiğinden, verilen kısıtlamalar için etkisizdir. k yeterince küçük, bu yüzden bir n kurtulmak için bir yol bulmaya çalışmalıyız.

Başka bir yaklaşım deneyelim. Ayrıca, dizimizdeki değerlerin üst sınırı olan S - var. Bununla ilgili bir algoritma bulmaya çalışalım.

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] 

Bu karmaşıklığı O(n * k * S) var, ama biz oldukça kolay O(n * k * log S) bunu azaltabilir. İhtiyacımız olan tek şey, öğelerin verimli bir şekilde özetlenmesini ve güncelleştirilmesini sağlayan bir veri yapısıdır: segment trees, binary indexed trees vb.