Poprawa algorytm usuwania elementu

Question

Problem

Podając łańcuch s i m zapytań. Dla każdego zapytania usuń K -po wystąpienie znaku x.

Na przykład:

abcdbcaab 
5 
2 a 
1 c 
1 d 
3 b 
2 a 

Ans abbc 

Moje podejście

używam drzewo bitów dla operacji aktualizacji.

Kod:

for (int i = 0; i < ss.length(); i++) { 

    char cc = ss.charAt(i); 
    freq[cc-97] += 1; 
    if (max < freq[cc-97]) max = freq[cc-97]; 
    dp[cc-97][freq[cc-97]] = i;     // Counting the Frequency 
} 
BIT = new int[27][ss.length()+1]; 
int[] ans = new int[ss.length()]; 
int q = in.nextInt(); 
for (int i = 0; i < q; i++) { 
    int rmv = in.nextInt(); 
    char c = in.next().charAt(0); 

    int rr = rmv + value(rmv, BIT[c-97]);    // Calculating the original Index Value 
    ans[dp[c-97][rr]] = Integer.MAX_VALUE; 

    update(rmv, 1, BIT[c-97], max);   // Updating it 
} 
for (int i = 0; i < ss.length(); i++) { 
    if (ans[i] != Integer.MAX_VALUE) System.out.print(ss.charAt(i)); 
} 

Czas Złożoność jest O(M log N) gdzie N jest długość łańcucha ss.

Pytanie

Moje rozwiązanie daje mi Przekroczono limit czasowy błąd. Jak mogę to poprawić?

public static void update(int i , int value , int[] arr , int xx){ 
    while(i <= xx){ 
     arr[i ]+= value; 
     i += (i&-i); 
    } 
} 

public static int value(int i , int[] arr){ 
    int ans = 0; 

    while(i > 0){ 
     ans += arr[i]; 
     i -= (i &- i); 
    } 
    return ans ; 
} 

Answer 1

Istnieją kluczowe operacje nie pokazane, i na to, że jeden z nich (całkiem prawdopodobne, że metoda update) ma inny koszt niż myślisz. Co więcej, twoja deklarowana złożoność jest z pewnością błędna, ponieważ w pewnym momencie musisz zeskanować ciąg znaków, który ma co najmniej O(N).

Ale tak czy inaczej, oczywiście strategia jest taka, aby przejść przez zapytania, rozdzielić je według znaków, a następnie przejść przez zapytania w odwrotnej kolejności, aby ustalić początkowe pozycje znaków, które mają być tłumione. Następnie raz przeciągnij łańcuch, emitując znaki tylko wtedy, gdy pasuje. To rozwiązanie, jeśli dobrze zaimplementowane, powinno być wykonalne w O(N + M log(M)).

Wyzwanie polega na tym, jak skutecznie reprezentować skreślenia. Myślę o jakimś drzewie względnych przesunięć, więc jeśli zauważysz, że pierwsze usunięcie było 3 a, możesz efektywnie wstawić je do drzewa i przenosić je później po tym usunięciu. Tutaj będzie bit log(M).