### secomo's blog

By secomo, history, 2 months ago,

Hi..

Given an array a that containes 2n elements each element has han an occurrence of 2 in the array.

so {1,2,4,1,4,2} would be an example, Now we have Q queries each query is asking for the maximum element on the segment L...R,but if the element has 2 occurrences on the segment L...R it will not be counted.

so if a={1,2,4,1,4,2} and query={2,6} the answer will be 1 because 4 and 2 will not be counted.

I think I can solve this uning Mo algorithm but I want a segment tree aproach.

Any help would be great, Thank you for reading.

• -1

 » 2 months ago, # | ← Rev. 6 →   0 Haven't tried it but I think this is the solutionUse a Segment tree to maintain a set of numbers for the appropriate range at each node. If the number has already appeared in both sets when combining, don't add it to the new combined set. As for queries, if Set is empty, then there is no appropriate number, else the answer is the last element in the set. Easy to do updates. UPD: My solution is slow
•  » » 2 months ago, # ^ |   0 Ii think it doesn't work in following case: array: 1 2 1 2. query: 2 4
•  » » » 2 months ago, # ^ |   0 You are right, just realized lol
•  » » » 2 months ago, # ^ |   0 wait, how is it wrong? I dont think its wrong since it has set S = {2} at left subtree and set T = {1,2}. Then combining gives you Set U = {1} so 1 is the answer
•  » » » » 2 months ago, # ^ |   0 How are you going to combine them faster than O(n)?
•  » » » » » 2 months ago, # ^ |   0 Its actually O(log(n)) time
•  » » » » » » 2 months ago, # ^ |   0 In worst case, you have to combine segs of length n/2 and n/4. So you need O(n) operations to combine them.
•  » » » » » » » 2 months ago, # ^ |   0 True, so then my solution is slow
•  » » » » » » » » 2 months ago, # ^ | ← Rev. 3 →   0 nvm, wrong
 » 2 months ago, # |   +16 Draw it in 2D and solve for the case when the answer segment is to the left of the query segment. Second case is similar.
•  » » 2 months ago, # ^ |   +6 Your solution is vague,could you explain in detail and examples what is the solution please?
•  » » » 2 months ago, # ^ |   +3 Suppose some number $k$ appears in positions $l_k$ and $r_k$, $l_k < r_k$. For each $k$ add a point $(l_k, r_k)$ with value $k$. For each query $[L, R]$ add a point $(L, R)$. Draw it for some sample, think for a while.
•  » » » » 2 months ago, # ^ | ← Rev. 4 →   0 I liked the change of view, so one + is from me, but it doesn’t mean I understood your approach. More to tell: solution region seams a little bit more complex than just “to the left of query point”. And there still a problem left — to find maximal value of those points in strange region in ~ log(n).Or did I misunderstand what should be drawn: Pic
•  » » » » » 2 months ago, # ^ |   +3 If you solve only for those $(l_k, r_k)$ that satisfy $l_k < L \le r_k \le R$ then the solution region is a rectangle to the left of the query point. Now there is the other case, where $L \le l_k \le R < r_k$. To solve this you reverse everything and realize that this is the same problem.