dreamplay's blog

A Query Problem.
By dreamplay, history, 7 years ago, In English

Hey there.

I have the following problem, not from any ongoing or past contest. Can you help me, by suggesting what optimal methods you have to solve it.

Node has three properties: left, right, height

N Insert node queries. Each query is (l, r, h).

Now M queries ask following: L, R, H
For all nodes(l, r, h), that satisfy L <= l && r <= R,
return min( abs( H — h) )

Can you guys suggest some approaches that you have in mind?

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

»
7 years ago, # |
  Vote: I like it +40 Vote: I do not like it

I don't know why you used node instead of item. Anyway, here is some idea:

The first thing which comes to mind is to solve the problem offline. Whenever you see queries with L ≤ l and r ≤ R or similar, sorting both items and queries by one of the endpoints and using sweep line should naturally cross your mind.

Let's sort all items and queries in order of decreasing l and L. Now let's loop over all queries in that order, say (L, R, H) is the current one. We should keep some data structure, in which we should add all items having l ≥ L and which makes answering queries simple. Notice how we have all items which meet the L ≤ l requirement inserted into our data structure. This kinda eliminates that requirement and in our data structure we only have to make sure that r ≤ R is met.

What is a suitable data structure which supports inserting (r, h) pairs into it and answering (R, H) queries quickly? It turns out that using a segment tree for minimum, where the indices are the h values and the values they hold correspond to the smallest r such that an (r, h) exists. Whenever we insert a (r, h) item, we assign to index h the minimum of its current value and r. Answering a (R, H) query is actually just finding the largest index less than H and the smallest index greater than or equal H holding values less than or equal to R, which is the well known binary search on segment tree.

Depending on the constrains on H and h, compressing those values beforehand may be needed in order to achieve O((N + Q) * log(N + Q)).

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

Thanks for your answer.

I should've mentioned, the problem needs to be solved online . Also, it would be helpful, if there is not a big constant factor involved, especially while insertion.

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

    Also O(1) solution would be preferred, I guess? Are you sure this is not a problem from any ongoing contest, "it must be solved online" sounds way too specific for a problem you came up with which couldn't solve at all?

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

      Hey, chill.

      I came up with it myself, due to some work related stuff and the reason I said for it to be online and not have much pre-computation is so that it is suitable for work/production related environment as that was the need if I later wanted to use this idea to be incorporated in my use.

      Anyways, that's okay.

      → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it -12 Vote: I do not like it

      I am not sure but this problem from ongoing Codechef Long Challenge seems quite similar.

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

        Can you point out one similarity besides "both tasks have N and Q"?

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

Is log^3(N) per query acceptable? If yes, it can probably be achieved using 2d segtree + sets or simply BIT + segtree + set

Edit: If we use what P_Nyagolov says, we can hit log^2(N) online. Just use a BIT of segtree's (index corresponds to l value) instead of processing in increasing order of l

→ Reply