Thắc mắc về iterator và solution n log n

[thangcachepckt (chickenanddog)]

Em đang cố dùng một data structure mà truy cập một giá trị của nó chỉ mất log(n) và tính toán cái vị trí (index) của nó (O(logn) hoặc O(1) time) trong cái data structure đó.
Em đã làm như này nhưng bị quá thời gian (O(n^2) do ::distance mất đến O(n)

multiset <long long> st;
loop -> (st.insert(number); ...
multiset <long long> :: iterator it; 
it = lower_bound( value) 
cout << distance (st.begin(), it); 

Mọi người chỉ cho em cách làm như này nhưng thời gian chỉ mất n log n không ạ? Em cảm ơn rất nhiều ạ

[noname00 (HK boy)]

Bạn có thể nói rõ đề bài hơn được không?

Mình nghĩ là thuật toán tìm index tốt tầm O(log n) là được, không cần cố O(1) vì rất khó.

[thangcachepckt (chickenanddog)]

Vậy có con trỏ it trỏ vào giá trị đó rồi thì tìm cái index của giá trị đó bằng logn trong cái data struct thì làm sao ạ

Em sửa để bài rồi ạ :DD

[noname00 (HK boy)]

Có nhất thiết phải dùng multiset không bạn? Nếu không thì bạn có thể tự cài 1 balanced binary search tree, có thể tính toán vị trí trong khi search luôn.

[thangcachepckt (chickenanddog)]

Dạ vâng em sẽ tìm hiểu về nó thử