protypuns's blog

Data structures problem
By protypuns, history, 9 years ago, In English

I was solving a segment tree problem in witch you are given:

Update L, R. — updates [L;R] with the value of the current operation (1, 2, ... M)

Query. — count different elements in [0; N]

N <= 10^7

M <= 4 * 10^4

I couldn't come with an aproach. I will be really happy if someone helps me with it. Thankd in advance! :)

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

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

this problem can be solved with set
imagine we have a set with pairs of two ints
in this set we have pairs of l and r's of segments and the segments are disjoint and every time we are asked to update a segment with an l — r query we will find the segments that intersect with it and are inside it and segments which include this segment with lowerbound on the set and remove the segments which are inside it and split the segments which include it and intesect with it the segments which we split are O(1) and every segment is removed with O(lgm) so it has an amortized order of O(mlgm) but how to answer the queries? in a map called cnt in cnt[x] we save the number of segments which have number x and whenever we remove a query we will decrease cnt[x] by 1 and if it hits zero we decrease the current answer by one every time they want the query we will just say the current answer

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

Problem link please?

→ Reply