MOOONI's blog

Help with a data structure problem
By MOOONI, history, 5 hours 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

»
5 hours 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
»
4 hours ago, # |
  Vote: I like it +1 Vote: I do not like it

segment tree.

→ Reply
»
65 minutes ago, # |
  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 a set or something to keep track of the label of the t-th element of v. From there on you can just use a merge-sort tree.

→ Reply