| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 155 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | djm03178 | 152 |
In Problem 877F , how to apply Mo's algorithm ? while traversing each block what to do ? editorial is not well explained .
Suppose a[] = { 1 , 1 , 1 , -1 } . We want to get all subarray's in the range 2--4 with sum = 1 .
Approach with HashMap would be linear complexity and total Time Complexity would be O(N*Q) if there are q queries.
**how to reduce it to sqrt. decomposition . **
Can you not use exclamation marks everywhere? It looks very rude.
first calculate prefix sums on each index
then start normal mo's algorithm,but in each step add or remove the prefix sum that you are on it
after that for each query you want to count the number of j's such that sum[i]-sum[j] = k,or you want to know the j's that sum[i]+k= sum[j],and you calculated this number before so you can easily answer each query
what is normal mo's algorithm , this is where i am having difficulty . since the problem can be solved using n*q time , by every time querying number of subaarryas with sum = k in the range L , R by the using prefix sum and hashmap.
but from here how should i reduce it to sqrt(N) , how to apply mo's algo. here , what to do ?
M_H_H_7
https://blog.anudeep2011.com/mos-algorithm/ Here you can learn about normal Mo's Algorithm.
But doesn't this blog is very specific , that is the algo have been applied only for the problem : count all elements whose count >=3.
how to deal with other problems .
doped.silicon
is mo's algorithm is just sorting the queries ? As Audeep mentioned that __ We are done with MO’s algorithm, it is just an ordering.
MO's Algorithm is just a smart way to process the offline queries in a certain order which reduces the overall complexity of the problem to O(Sqrt(N) * N). If we don't sort the queries and solve the problem the complexity will remain O(N^2).