•Kira96
Client obisnuit
Karma: 36
Deconectat
Mesaje: 69
|
|
« Răspunde #36 : Ianuarie 26, 2015, 18:36:31 » |
|
Ok, o sa pun aici solutia la kthvalue cu alb, pentru cei ce nu doresc spoiler.
In primul rand sa consideram posibile doar urmatoarele operatii: se adauga la sfarsit un element, se sterge ultimul element, query l,r,k sa se afle al klea element din intervalul [l,r]. Problema asta se poate rezolva in MlogN, unde M=numarul de operatii si N=valoarea maxima a unui numar. Puteam stoca intr-o trie, dupa x adaugari sa zicem, toate cele x numere adaugate (tria va avea doar 0 si 1, daca nu stiti cum faceti asta, cititi problema xormax ). Acum, daca am putea mentine cate o trie pentru starea sirului de numere dupa x adaugari, adica o trie pentru fiecare prefix al sirului, problema ar fi rezolvata : parcurgem simultan tria pentru prefixul [1,r] si cea pentru prefixul [1,l-1] si daca scadem din frecventa primei trii, pe cea a celei de-a 2a aflam practic cum arata tria pentru intervalul [l,r]. Acum, putem sa facem un "dfs" simultan pe cele 2 trii si vedem daca mergem pe ramura cu bitul 0 sau cu bitul 1. Acum, la problema noastra trebuie sa facem cateva modificari. Poate se realizeaza mai usor dar o sa va zic cum am facut eu : Mentinem 2 astfel de trii, una pentru adaugari in fata, cealalta pentru adaugari in spate. Problema s-ar pune atunci cand stergem un element dintr-o parte si acea trie e deja goala, dar cand intervine acest caz "resetam" tria cu numarul 0 din partea opusa, adica incrementam ordinul triei considerate 0.In fine, destul de smechera problema, GG propunatorilor.
|