where is QCHEF editorial?
4 Likes
Can anybody please let me know what were the prerequisites for solving this problem?
I guess the editorial will be published soon. I have solved the problem using the SQRT decomposition principle. My complexity was (N* sqrt(N) + Q * sqrt(N) * log (N)). I am wondering if there exists a better approach, that is, is it possible to get rid off the log(N) part? I have tried the Mo’s algorithm also, but that did not work for me.
1 Like
solved using segment tree.
2 Likes
I dont understand why people complicate things by attaching heavy names to simple techniques. This question simply requires basic square root decomposition (I prefer this name to MO’s algorithm). my solution works in N*sqrt(N) and is 80 lines only.
2 Likes
editorial is out !!!
editorial out
pre-requisites :
sqrt decomposition, preprocessing
MO’s algorithm i think
I got rid off the log(N) part easily. Notice that only sqrt(N) parts are really affected … so for each query you want to check the sqrt(N) parts that were affected, and not all of them.
A really vague explanation, but maybe you had a similar idea, so you will get what I mean 
I thought it can not be solved using segment trees… Can you please explain your approach? Either here or on the editorial page once it is served?
it,s simple O(N) solution that anyone would think first.Key points
use of hashing where index and query number are hashed
isnt the worst case complexity n^2
if input is like
7 6 n
1 2 3 4 4 5 6
1 7
1 7
1 7
all queries are from beginning to end
and only repeting growth is in the middle
1 Like
Yes that is why I am asking how it got AC?
Hi All, we apologize for the situation. We will add strong test cases in the practice session.
1 Like