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.
Haven't tried it but I think this is the solution
Use 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
Ii think it doesn't work in following case: array: 1 2 1 2. query: 2 4
You are right, just realized lol
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
How are you going to combine them faster than O(n)?
Its actually O(log(n)) time
In worst case, you have to combine segs of length n/2 and n/4. So you need O(n) operations to combine them.
True, so then my solution is slow
nvm, wrong
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.
Your solution is vague,could you explain in detail and examples what is the solution please?
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.
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:
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.
Looks very interesting task. please provide link for this task if available
This task is created by me ..
when I was solving some tree path problems I faced this problem.
I think it may be solved with lazy propagation if you can answer queries in order of their right point: You can traverse array from left to right and when you first encounter a number you put it in segtree and memorize its index of occurrence. And when you meet a number that already memorized to be on a position i, you delete it from i (substitute with -inf or what should be answer for a query with only paired numbers?) and lazily propagate value of this number on range [i+1…n].
And then you answer all the queries that ends (r) in current point with max result among range query [l, r] on segtree of first occurrences, and point [l] query on lazy segtree. And proceed with next point.
Not sure why people downvoted this blog, maybe it's the "they are grey so let's downvote"-syndrome. This problem is actually pretty interesting.
I thought on a solution with persistent segtree (if you never seen it imagine it as storing all the versions of a segtree after doing the updates in a way that is not terrible). Let's make 2 persistent segs called segL and segR. Let segL[i] have the value of the second appearence of a number if it appears from i to n and 0 if both appearences happen in that range (for example, segL[3] would hold {0,0,0,1,0,2} in the example) and segR[i] be the same thing from 1 to i (segR[4] would hold {0,2,4,0,0,0}).
The answer of a query of [l,r] would be max(segL[l].query(r),segR[r].query(l)). The reason for that is that a number will only appear in two cases:
That way we can do it fairly simply in O(nlogn) which is much better than the mo solution