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 .

# | User | Rating |
---|---|---|

1 | tourist | 3947 |

2 | jiangly | 3740 |

3 | Radewoosh | 3652 |

4 | Benq | 3626 |

5 | jqdai0815 | 3620 |

6 | orzdevinwang | 3612 |

7 | ecnerwala | 3587 |

8 | Geothermal | 3569 |

8 | cnnfls_csy | 3569 |

10 | ksun48 | 3485 |

# | User | Contrib. |
---|---|---|

1 | awoo | 163 |

2 | maomao90 | 160 |

3 | adamant | 156 |

4 | atcoder_official | 155 |

5 | nor | 154 |

6 | cry | 153 |

7 | maroonrk | 152 |

8 | SecondThread | 148 |

8 | -is-this-fft- | 148 |

10 | Petr | 146 |

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 .

↑

↓

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/16/2024 06:22:41 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

I think it can be solved by

Mo algorithmSort queries by this comp:

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.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:

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).

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

I know this is probably just an example code but I want to point out that

sqrt(n) would return a double, and most probablyx.l/sqrt(n) will be converted to a double itself, so the "!=" comparison may not produce correct results.Use (

int)sqrt(n) instead :)Oh, that was a stupid mistake. I usually use

`int sq=sqrt(n);`

and then usesqin comparisons just because of that casting but this time I somehow forgot the (int), thanks for the correction! :)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

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 )

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.