MOOONI's blog

Help with a data structure problem
By MOOONI, history, 3 weeks ago, In English

There is a vector of intervals (called v) that is initially empty. There are Q queries to process. two types of queries might appear:

  1. Insert an interval (x, y) to an arbitrary place in v. (1 <= x <= y <= 10 ^ 5)

  2. What is the last interval among the first t elements in v, that contains the number x?

the number of queries is at most 10 ^ 5

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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

segment tree.

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

First, process all type 1 queries according to their final position. For example, if the queries are of the form:

type=1 x=1000 y=1000 index=1

1 1000 1000 2

1 1000 1000 1

label the first interval as interval 2, the second as interval 3, the third as interval 1. Then, for each type 2 query, you can use an ordered set or something to find the label of the t-th element of v. From there on you can just use a merge-sort tree.

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

    I think you've assumed that t is constant. But it's actually variable

    → Reply
    • »
      »
      »
      3 weeks ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      if you use an ordered set instead of set, the same approach should still work

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

To solve this problem let's consider simpler query, suppose we only do insert interval on back (push_back) for first query and we only want to know the last interval index containing number x on current vector. Solving this query is easier and can be done using segment tree. To solve this we can maintain array A of size 10^5 with value A[i] = what is the last interval index that contain i. To solve the query we can do range_set(x, y, interval_idx) for first query and just access A[i] for second query.

For our next target is to solve first query for some arbitrary index insertion. To simplify the intervals indexing we can first compute for each interval, what is their index on the final array. For updating our array A, we can do change_max(x, y, interval_idx_on_final_array) (i think this operation can only be done using segment tree beats), our second query is still same. Now for solving the normal second query that is only considering only the first t intervals, we can maintain persistent segment tree to store historic data and we can do previous point query idea on the t-th persistent segment tree.

You can correct me if i'm wrong or if you have better idea without using segment tree beats or persistent segment tree. I don't think solution using range update persistent segment tree can easily pass if the TL is tight. Maybe you can also give the problem link so that i can try submitting my solution.

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

    We don't need to do max= (just raw =) because we the new index will always be the maximum

    *Persistent segment tree should easily pass here

    → Reply
»
3 weeks ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

if offline is allowed then you can do a sweep:

push back all interval endpoints and values of x into a vector, sort it, loop over it:

if it's the <start/end> of an interval, <insert/erase> the interval <into/from> a data-structure

if it's an x value, well we have a data-structure of all "active" intervals. the query now is: only consider intervals which were inserted into v before the query, and have index before t, looks like a 2D query, solvable with merge sort tree

→ Reply