secomo's blog

Max of a segment with something new
By secomo, history, 3 years ago, In English

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.

  • Vote: I like it
  • -1
  • Vote: I do not like it

»
3 years ago, # |
← Rev. 6   Vote: I like it 0 Vote: I do not like it

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

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

    Ii think it doesn't work in following case: array: 1 2 1 2. query: 2 4

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

      You are right, just realized lol

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

      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

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

        How are you going to combine them faster than O(n)?

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

          Its actually O(log(n)) time

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

            In worst case, you have to combine segs of length n/2 and n/4. So you need O(n) operations to combine them.

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

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.

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

    Your solution is vague,could you explain in detail and examples what is the solution please?

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

      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.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
        ← Rev. 4   Vote: I like it 0 Vote: I do not like it

        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
        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          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.

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

Looks very interesting task. please provide link for this task if available

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    This task is created by me ..

    when I was solving some tree path problems I faced this problem.

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

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.

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

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:

  • r is smaller than the second appearence and l is smaller than the first appearence (covered in segR[r].query(l))
  • l is bigger than the first appearence and r is smaller than the second appearence (covered in segL[l].query(r))

That way we can do it fairly simply in O(nlogn) which is much better than the mo solution

→ Reply