How solve subtask3 using online varient MO’s algortihm??
1 Like
As far as I have understood from resource 2 for online Mo’s algorithm, the mentioned solution for this problem [100 pts.] is almost same, with the difference that block size is \sqrt n instead of n^{2/3}
Is it true ?
1 Like
Try with block size \le 350. Actually when the block size increases the cost of answering the query will also increase ``because we need to traverse the first and last block of current query and update the answer. So, naturally lesser block size means less number of iterations.
The tradeoff is in pre-calculation, as the number of blocks will increase [decrease block size], however, it doesn’t seem to affect much. Overall you get a speed up.
See these two solutions where you’ll notice the difference: TLE [\sqrt n block size], AC [BS = 300]
1 Like
Try with block size ≤350. Actually when the block size increases the cost of answering the query will also increase ``because we need to traverse the first and last block of current query and update the answer. So, naturally lesser block size means less number of iterations.
The tradeoff is in pre-calculation, as the number of blocks will increase [decrease block size], however, it doesn’t seem to affect much. Overall you get a speed up.
See these two solutions where you’ll notice the difference: TLE [√n block size], AC [BS=300]
Additionally, don’t use prefix sums to calculate counts of each number for block [l...r], instead use a vector to store indices for each element, and do binary search. I know the latter is slower for query, however, the test cases does seem to have a lot of distinct numbers in the given array which makes frequency of each element very less and so binary search is almost O(1)
2 Likes
@thefallenstar i have set the block size to 300. I am still having the same issue with same cases passed as before.
read about sqrt decomposition
Actually my comment was meant for @abhayps and not for you [where last subtask gets TLE].
As for your code is concerened, it is slow at a lot of places. I think you should be using ordered map instead. Unordered has sometimes O(n) access time. Besides, you don’t even need it. Check out my AC submission [above].
Mushkil h! Namumkin Nhi…
1 Like