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

offline solution
Автор speedster, история, 9 лет назад, По-английски

How to solve this: given multiple query of type : x l r , we need to find the frequency of x in the range r to l. There are no updation so basically calls out for an offline algorithm .

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

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

I think it can be solved by Mo algorithm

Sort queries by this comp: 

bool comp(Query x, Query y) {
    if (x.l!=y.l) return x.l < y.l;

    return x.r < y.r; 
}

Let freq[i] be the frequency of number i, you can now solve the problem by shifting the previous L,R query to the curL, curR and then answer the query.

→ Ответить
  • »
    »
    9 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

    What your comparing function does is not what Mo's algorithm is supposed to. You can't simply sort the queries as pairs and expect this to work fast. The correct function goes here:

    bool comp(Query x, Query y) {
    if (x.l/(int)(sqrt(n))!=y.l/(int)(sqrt(n))) return x.l < y.l;

    return x.r < y.r; 
}

    For example, if N=9 and there are queries (1,9), (2,4) and (3,6), then they should be in order (2,4), (3,6), (1,9) or (1,9), (3,6), (2,4) but your function will sort them like (1,9), (2,4), (3,6).

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      Oh you're right, that was my mistake, thanks.

      → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      I know this is probably just an example code but I want to point out that sqrt(n) would return a double, and most probably x.l / sqrt(n) will be converted to a double itself, so the "!=" comparison may not produce correct results.

      Use (int)sqrt(n) instead :)

      → Ответить
      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится +11 Проголосовать: не нравится

        Oh, that was a stupid mistake. I usually use int sq=sqrt(n); and then use sq in comparisons just because of that casting but this time I somehow forgot the (int), thanks for the correction! :)

        → Ответить
»
9 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

for each number in the input array, store the indices where it's present in a vector. for each query x l r, the answer will be upper_bound(r) — lower_bound(l).

what is an offline algorithm?

try this problem: https://www.hackerrank.com/contests/codeagon/challenges/sherlock-and-subarray-queries

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

sorting query with square-root decomposition gives O( n ^ 1.5 )

There is online solution with O ( n lg ^ 2 n )

first, store each step of merge sort such as

3 1 4 1 5 9 2 6

( 1 3 ) ( 1 4 ) ( 5 9 ) ( 2 6 )

( 1 1 3 4 ) ( 2 5 6 9 )

 ( 1 1 2 3 4 5 6 9 )

then, [l, r] can be decomposed to O (log n) intervals with 2^k sizes. for example, [3, 6] (0-based, inclusive) can be decomposed to [3,3], [4, 5], [6, 6] you can add up all upper_bound(x) — lower_bound(x) for each interval and that is answer.

→ Ответить