Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

I_LOVE_METSUKA's blog

Please help
By I_LOVE_METSUKA, history, 9 years ago, In English

I want to add numbers to a set of integers and answer a query how many numbers are there which are less than a given number K. What is an efficient way to implement this other than BIT?

  • Vote: I like it
  • -38
  • Vote: I do not like it

»
9 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

I don't know what is BIT, but you can simply use a vector as a set (find exact position for a newer element using lower_bound and inserting if element at this position isn't equal to the one you're trying to add). Then, just using distance(vect.begin(), lower_bound(vect.begin(), vect.end(), K)) — you can obtain the answer for a query.

→ Reply
  • »
    »
    9 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it +7 Vote: I do not like it

    inserting in the middle of a vector is O(n).

    → Reply
    • »
      »
      »
      9 years ago, hide # ^ |
      ← Rev. 3  
      Vote: I like it 0 Vote: I do not like it

      Well, yes. Then, you could insert in a set first, then do copy(iset.begin(), iset.end(), back_inserter(vect)) and perform queries on the vector as stated above. I expect copying to have linear complexity.

      → Reply
»
9 years ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

C++ STL: Policy based data structures

→ Reply
»
9 years ago, hide # |
 
Vote: I like it +21 Vote: I do not like it

Using a treap to implement a set(set in STL),it is O(log n).

→ Reply