Блог пользователя rofi93

Автор rofi93, история, 8 лет назад, По-английски

Problem: You are given an array consisting of n elements and q queries in the form of [L,R]. You have to output the maximum occurrences of a number in the segment [L,R] for each query.

How to solve these kind of problems using Segment Tree ?? I can solve this using sqrt decomposition, but got stuck trying to solve using segment tree.

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Still thinking about how you would do it with a segment tree, but here is a way you can do it in log n:

Store each number in an array of vectors, with the array indexed by each value in the input array. (You can use a map if values are very large.) In the vector you store the index of the respective value. You can binary search for the lower bound and upper bound of the segment in the vector and subtract their indices to get the answer.

The problem is that update queries are slow.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Wouldn't that output just the occurence of a particular number in the segment? But I thought he asked for the maximum frequency of all possible numbers in that segment..

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Oh...Seems like I misread the problem :/

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        May be i couldn't describe the problem well enough. I want to find the mode number (most frequent number) and the times it occurs in the given segment.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Maybe I'm misunderstanding the question, but wouldn't you need to check all (up to N) numbers after doing this?

    rofi93, what is your sqrt decomposition solution? The best solution I see is O( ( N + Q ) sqrt N log N).

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      You can do it using MO's algorithm with complexity. Let's compress coordinates and store for each number it's frequency (easy to update), and for each frequency list of numbers with this frequency in linked list. Because it's linked list we still can do updates in O(1) time, because we can store pointers for all numbers and find number in linked list in O(1) time and move element to other list in O(1) time. Now we just need to find list with maximal frequency which is not empty. Key idea is if we changed one element (like we do in MO's algorithm), answer can change only by 0, 1, -1. So if last answer was x, we just need to check if x — 1, x, x + 1 lists are not empty.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      My sqrt decomposition solution is O((N+Q)sqrt N).

»
8 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Found a link to similar discussion here. http://codeforces.me/blog/entry/19710?#comment-245484

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Read the solution for problem PATULJCI. I think that is what you need.