A, scuze, problema e ca nu are voie sa fie amortizat. Interesant..
Am putea in loc sa folosim memorie suplimentara, sa folosim tot memoria in care incap U intregi.
Presupunem ca intregii din uvec sunt destul de mari, sa zicem cel putin max[log(2N)+1, log(U)+1] biti, deci pot tine numere de la -2N la +2N sau de la -U la U.
Tinem max ca la solutia initiala.
Intregul i e in multime daca:
* i < max si uvec[i] este negativ
sau
* i >= max si 0 <= uvec[i] < max si abs(uvec[uvec[i]]) = i
Deci ideea e ca folosim primii max intregi ca storage, si mai folosim un bit (semnul negativ) pentru numerele din zona asta.
Inserare:
* daca i < max: uvec[i] = -abs(uvec[i])
* daca i >= max:
- flag = contains(max) // verificarea de mai sus, O(1)
- uvec[max] = i; uvec[i] = max;
- daca flag sau (i == max): uvec[max] = - uvec[max]
- max = max +1