@nilesh3105 https://www.codechef.com/viewsolution/18279391 You can look at it here.
Although there is code copy pasted trice and poorly commented. But its sqrt decomp. If you want exactly O(Nsqrt(N)). Just do a change in value of C in first line.
If someone wants to visualise @vijju123 's O(n) soln working. https://ideone.com/Sxb6w8 . I have added enough printf statements after each operation such that it can be visualized.
P.S.- I was able to understand this only when run printed everything.
I accidentally gave @admin wrong link and didnt realize it till now. I had a commented solution for easier understanding. Will update editorial to add that.
Thank you for your initiative aryan 
1 Like
The base of the solution is that, we are maintaining in the deque elements in form such that we can execute query from one part of deque to another. In case of any violation, we remove the required elements. You can also look at tester square root solution - it feels a lot more natural in thinking as well
One of my incentives to give 3 approaches. Even if one of them is understood, then editorials job is done. Rest can be left for interested ones
1 Like
square root was the one which I used during the contest. And what I feel is that square root and Segment Trees goes hand in hand. With proper choice of bucket size. Question can be done using square root which is intended for Segment Trees. If time limit is not very tight.
1 Like
Thats true, though I feel Segment tree is more intuitive if you know the golden rule for it. Square root always tends to give me implementation headaches xD
Can you please provide us Golden Rule ?? Because I always get intuitive for Square Root. And end up implementing it. And find soln with segment tree used.
Its a secret which I found after digging 10 blogs on seg tree 
.
On a birds eye view, just about nodes.
1 Like
Okk. You live with secret. I live with "On a birds eye view, just about nodes."
Nah, I wanted to see what youâd say on that I have no right to keep it secret since I came to know it because someone else shared
"Its all about defining relationship between child and parent nodes. What data should I store, so that using that, if I have data of child nodes, I can derive data of parent node. The base cases, are leaves, and are trivial. If we get the relation, we can advance from leaf to next leve, from there to nextâŚand hence to the root. You can, surely, make ad hoc solution, but this is the concept of segment tree which will help you throughout "
2 Likes
I guess i have read these lines from the same source as vijju123
PS: Nice concept âChef vijjuâs cornerâ. Your editorials are such a beauty.
1 Like
Googling - segment tree golden rule. Takes me here https://discuss.codechef.com/questions/103871/how-to-start-with-segment-trees
Awwwh. Thank you @taran_1407 . Its a big compliment hearing you liked them :). Yup, Chef Vijjuâs Corner started from my first editorial which I wrote for ICPC Amritapuri ones- because practically I was a free soul there. @admin and @dpraveen mentored me a lot, and they let me have my scope of creativity. Since then, I try to mention anything - which I cant mention in official part due to length issues- in bonus section. I feel it might be useful to some
Nice catch @aryanc403 xD xD. Very impressive! 
1 Like
Can you please post the link to your solution? Also why did you use co-ordinate compression here?
I need help, i donât know why my algorithm doesnât work.
I can explain what it does if you need. Thanks in advance :D.