Author’s Solution can be found here
13 Likes
Thanks for the editorial, I have come across a similar question on hacker earth with stricter constraints :
the author’s solution gives SIGSEGV even after changing chunk vector size (1000) , editorial on hackerearth seems to do something different with 2 fenwick trees any help on explaining hacker earth approach or modifying author’s solution to pass it on hacker earth will be much appreciated
1 Like
Any similar problems for practice?
@karan173 There are many problems which can be solved using the “trick” for offline queries as described in the editorial. Some of them are:
Chef and Substrings : CodeChef: Practical coding for everyone
Tree and Queries : Problem - D - Codeforces
Jeff and Removing Periods : Problem - D - Codeforces
1 Like
Thanks for replying and for the great editorial! Will look at the problems!
Can anyone give me the offline approach solution? Can’t understand the query and update portion clearly…
u have to apply mo’s algorithm for solving queries.
in which u divid the array into blocks of su=ize sqrt(n);
and for any specific query u have to maintain segment tree or BIT tree.
and this is easily available on gfg!!
my code link:: CodeChef: Practical coding for everyone
lol you mixed two solutions and make one 
This question is a combination of MO’s, BIT, and little Bit math.
If n, q <= 3e4, is there any algorithm not using Mo’s Algorithm???