zerow's blog

By zerow, history, 7 months ago, In English

So I was solving a question, and in that question I basically had to find the kth available index after in each operation, and then occupy that index, basically removing it from the available indices.

Example:- Available indices : 0 1 2 3 4 5

1st Op: Find 2nd available index

Ans: 1
      Now available Indices: 0 2 3 4 5

2nd Op: Find 3rd available Index

Ans: 3    
    Now available indices: 0 2 4 5

I implemented a segment tree to solve this and then applied binary search to find the index where the SUM=INDEX WE NEED TO FIND.

I just built a SUM segment tree,set the value of each node to 1, and then found the sum of segments. After each operation, I set the used index to 0 and then just updated my segment tree as such:

 // I built the SUM segment tree with each value in the array set as 1 and then calculated the SUM of SEGMENTS

        int lo=0;
        int hi=n-1;
        int ffns=hi;
        while(lo<=hi){
            int mid=(lo+hi)/2;
            int p=query(1,0,n-1,0,mid);   //the query command which returns the sum of the segment
            

            if(p<v[i].second+1){
                lo=mid+1;
            }
            else{
                hi=mid-1;
                ffns=mid;
            }

        }
    
        fns[ffns]=v[i].first;
        update(1,0,n-1,ffns,0);      // update just sets the value of the index which we found to 0

However, I feel like I could remove the binary search part and just implement the segment tree in such a way that it helps me find the kth available index without having to use binary search.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by zerow (previous revision, new revision, compare).

»
7 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Go to EDU above, go to segment tree section. There's the solution of finding the kth one which is what you need here

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No way man, I had tried that but just made a small error in my code which was giving a different value from what I needed. Thanks for the quick comment!