where is QCHEF editorial?

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.

solved using segment tree.

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.

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

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.

Hey Alankar63, you can find the editorial here: http://discuss.codechef.com/questions/66188/qchef-editorial