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.
Now remove $$$O(n)$$$ part from your complexity. Can you do that?
ur gonna have to help me with that
Hint: use quantum computer.
You complexity is $$$O(qlogn + ...)$$$ and as explained, $$$q = O(n\sqrt{n}))$$$. Your algorithm is even worse than his original idea.
We're not going through all the queries everytime
ok my bad i just realized
if we already knew all the elements, couldn't we just concatenate the array and process as normal though?