structuri de date?

[•Andreid91]

Exista vreo structura de date care sa suporte un querry gen : a, b, x ? (cate elemente de pe un interval (a,b) sunt mai mici decat un x? nu este acelasi x pt toate intrebarile, am m intrebari, si pt fiecare,x-ul e diferit ) 

Ms fain 

 

[•Mishu91]

Cred că se poate rezolva cu AIB în 2 dimensiuni. O dimensiune o consider valoarea și una poziția, iar când fac un query fac o interogare pe intervalul (a, 1), (b, x). Dezanatajul este că ai O(N * Valoarea_maxima) memorie, ceea ce în general este cam mult.

[•devilkind]

Poti sa faci offline. Citesti toate query-urile inainte si le sortezi dupa valoarea X. Acuma tii un AIB in care initial toate valorile sunt 0 si cum parcurgi query-urile iei toate elementele mai mici decat x si le faci 1. In felu asta un query pe intervalul [a...b] iti va da numarul de numere mai mici decat x. Complexitatea finala ar fi O(N + M log N). Singurul dezavantaj e ca trebuie sa citesti query-urile inainte.

[•wefgef]

Solutia data de devilkind este cea mai buna in cazul in care nu ai update-uri si poti citi query-urile dinainte. Altfel, poti sa faci cu arbori de intervale 2D, folosind O(N log N) memorie si avand complexitatea de O(log^2 N) pe query/update.

[•Andreid91]

Da... o memorie n* max_val ar fi destul de mult  .  Destul de interesanta ideea cu AIB totusi...

Solutia lui devilkind e intradevar si mai usor de implementat, si ceva mai eficienta. 

Am sa ma uit si peste un articol cu arbori bidimensionali...par destul de interesanti si utili 


Ca tot veni vorba de intervale...m-am tot gandit si la problema asta, dar nu i-am dat de cap...
Cum pot rezolva un querry : determinati numarul de elemente distincte dintr-un interval (a,b) ? Am vazut ceva de genu si la baraj in a doua zi de concurs...

[•pauldb]

Exista o problema foarte asemanatoare cu cea de care intrebi tu pe site. Solutia ei e prezentata in acest articol.

[•Andreid91]

mersi Paul   

[•Mishu91]

Eu am rezolvat problema de care zici (cea de la baraj) in O(NlogN) in mod asemanator cu solutia prezentata de devilkind. Am sortat query-urile si le-am rezolvat in ordine.

[•wefgef]

Eu am rezolvat problema de care zici (cea de la baraj) in O(NlogN) in mod asemanator cu solutia prezentata de devilkind. Am sortat query-urile si le-am rezolvat in ordine.

Inseamna ca trebuie sa schimb testele .

[•Mishu91]

Cu parsarea citirii + câteva optimizări se pot scoate timpi sub 0,8 secunde, după cum se vede aici. Totuși, sunt curios de soluția in O(Nlog*N). Cum se face cu mulțimi disjuncte, fără a mai sorta intervalele?