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

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

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
  • Проголосовать: не нравится

»
11 лет назад, скрыть # |
← 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.

→ Ответить
  • »
    »
    11 лет назад, скрыть # ^ |
    ← 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).

    → Ответить
»
11 лет назад, скрыть # |
 
Проголосовать: нравится +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

→ Ответить
»
11 лет назад, скрыть # |
← 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.

→ Ответить