arbcrt040's blog

data structure problem
By arbcrt040, history, 9 years ago, In English

Greetings.

I was trying to solve one problem, but couldn't. It's like the RMQ problem but with add at position operation.

There are 2 operations:

ADD i X ---- ads X after ith element.
QUERY l r ---- RMQ of [l; r].

Can someone help me, please? Thanks in advance.

(Sorry bad English)

EDIT: Thanks everybody for help! Got accepted :)

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +46 Vote: I do not like it

Can you solve this problem?

  • REMOVE i -- remove the i-th element
  • QUERY l r -- RMQ of [l, r]
→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Couldn't :(
    Can you explain your approach.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Use a segment tree, and in addition to storing the RMQ, store the size of the un-deleted nodes.

      Then you can answer those queries by walking the tree. To remove an element, set its value to 0 (or ∞) and decrease its size by 1.

      Do you see how to reduce the original problem to this problem?

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Got the task for deleting, but how to reduce the original problem?

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

          Do all "Add" queries, go in reversed order, if the current query is adding set the val of i + 1th element to INF, increase all numbers of of array d from 1 to i + 1 by 1, if the query is rmq, then get the rmq between l and r + d_r

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

Say, the original array is A[] . Find the total number of elements that would be added between every two original A[] elements . Make an array B[] of size total elements of final array such that B[0]  =  A[0], B[0  +  AddedBetween(0,  1)]  =  A[1] and so on and fill the values in between according to the queries which is easy to do... Now make a RMQ segment tree that also stores the number of deleted elements in the interval (L,R) . So While querying for RMQ you would actually do RMQ(L,  R  +  deleted(L,  R)) to get the answer.

This was for reduction to the solution mentioned in the comments.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Sorry, I think your solution is wrong. You said RMQ ( L, R + deleted (L, R )), you don't know whether exist more deleted numbers between (R, R +deleted (L,R)).

    I hope you understand what I told you :)

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks! How to reduce it using segtree as zxqfl mentioned then ?

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I wrote down my solution, you can see it. I use binary search and BIT, maybe exist something smarter :)

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

          I can modify my method by finding smallest X using binary search such that undeleted(R,R+X) = deleted(L,R) and then do query(L,R+X) . Maybe this would work.

          → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can know the position of every added element by using seg tree and greedy sol somehow.

    So you have the whole array with nrelem+nr added full of 1,and for the last add you surely know that the (i+1)th elem is the position for the last added.Ok ,we make 0 at that position,and we have 1 in seg tree just for the remaining elements.(we do this in reverse order)

    Now the position of the next added element is the position of the (i+1)th 1 in seg tree,and this can be found easy,just a normal query function.We make 0 at that position and so on.You see?

    Now that we know all positions, we can answer easily to queries with another seg tree.

    I don't know if seg tree works for all possible use of rmq(like gcd), because you don't know what to put at positions which are not occupied at the moment so that it doesn't change the answer.

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

      There is also an sqrt-deomposition solution that our good friend MirceaFF didn't mention. We can divide into sqrt segments. When an element comes, you see the bucket where he belongs and put it there, for this of course we will use sqrt Queues. And from sqrt to sqrt Updates we kind balance the buckets because some of them will become too big. When [l,r] comes, we take the maximmum from the whole buckets and the rests from the other possible 2 buckets. o(m * sqrt(n+m)). But of course FF's solution is good and quite intuitive too, you just solve the queryes and updates backwards.

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

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

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

Could you please give me the link of this problem?

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

It can be solved using treaps or using SQRT decomposition

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you please explain how is it the solution using treaps?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      http://threads-iiith.quora.com/Treaps-One-Tree-to-Rule-em-all-Part-2

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Wow, that's an amazing tutorial. Thank you very much.

        I also would like to know the solution using sqrt decomposition. Could someone please explain me?

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

          We will build sqrt decomposition on our array;

          Then after insert operation we will just insert in needed block new element;

          After every sqrt inserting operations we will rebuild our decomposition;

          RMQ is same as in simple sqrt decomposition;

          Here is my code

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

I don't understand solution wtih seg. tree ( I don't get up, how we can find interval [L,R] in O(1)...

I'll write my solution, I think that is correct:

We can solve it with BIT + binary search + seg. tree. At first we find how many numbers we will add between any two number in starting array. After that we put everything in BIT ( if we haven't added some element yet we write 0, else we write 1). For the first query we update seg. tree and BIT ( in bit for updated position in array we write 1, in seg. tree we change node value for that position from inf to x). For the second query we find needed interval with binary search in BIT, after that we use RMQ in segment tree and find answer :)

Can you tell me, how I can solve it without BIT ?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can use another segment tree insead of BIT, then binsearch won't be needed. Just traverse tree from the root. Then you can find interval [L,R] in O(log) instead of O(log^2).

    But in practice BIT+binsearch is really fast, even can be faster than segment-tree.

    → Reply