| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3904 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3494 |
| 8 | Um_nik | 3396 |
| 9 | gamegame | 3386 |
| 10 | maroonrk | 3350 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 164 |
| 1 | cry | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 159 |
| 5 | awoo | 158 |
| 6 | adamant | 157 |
| 6 | -is-this-fft- | 157 |
| 8 | nor | 154 |
| 9 | TheScrasse | 153 |
| 10 | Dominater069 | 152 |
Is this problem doable with less than $$$O(n\sqrt{n}log(log(n)))$$$ time?
Given an array $$$p$$$, assuming $$$p_i=O(n)$$$. The array is cut to $$$O(\sqrt{n})$$$ blocks.
There is only one kind of query:
$$$1\ i\ j\ k$$$: Count the numbers from block $$$i$$$ to block $$$j$$$ such that $$$p_k$$$ is a multiple of (the query must be done in $$$O(1)$$$).
Any help is appreciated.
Just don't split it into blocks, you can do it in O(nlog^2) with offline queries
Is the queries guranteed to be $$$O(1)$$$? Because i need to do $$$O(n\sqrt{n})$$$ of them.
Is it online? if not, why?
It doesn't need to be online
Then you can just not split it into blocks and process it in $$$\mathcal{O}(n \times log^2(n))$$$
Can you give more details about the solution
I'll assume we're working within a reasonable limits here, where $$$1 <= n, a_i <= 2 \times 10^5$$$
We can store all of the positions of an element in a vector/array, let's call the array $$$pos[k]$$$. We can now find the occurrences of number $$$k$$$ in $$$log(n)$$$ by binary searching through the array.
As we're processing the queries offline, first we need to store the queries in an array, let's call $$$queries[k]$$$ the queries where we need to find the divisors of $$$k$$$. We can now simply iterate from $$$1$$$ to $$$max(a)$$$ and iterate through the multiples of it, in which we'll iterate through the queries and answer them.
Total time complexity: $$$\mathcal{O}(n \times log^2(n))$$$ because we'll be iterating through $$$n + n / 1 + n / 2 + ... + n / n \approx n \times log(n)$$$, and it takes $$$log(n)$$$ to answer each queries.