This question made me learn a lot . I wish there are more questions like XRQRS and SEALCM inplace of the first 6 questions that were there in this contest in the next long contest .
Really an awesome questionā¦Learnt a lotā¦In fact tried different data structures for the problemā¦
But even after implementing the solution as mentioned in the editorial, still getting TLE for one last test case. Canāt think of any further optimizations.
The link to the solution : http://www.codechef.com/viewsolution/5882154
Iāve managed to solve testcases where M <= 5 * 10^4. I used a combination of segment tree and trie.
Each segment tree element has a trie which contains all elements in that segment. This gave me a solution with time complexity O(logn * #bits) for all queries but kāth element. For kāth element Iāve used a binary search in combination with query of type 3 (#elements <= x).
Iāve also compressed trieās edges so that it looked more like suffix tree. It performed about ~2 times faster than uncompressed version. solution
Thereās a fairly simple (but apparently too slow) solution in O(log M log x) per query.
Just make a segment tree / RMQ-like structure of binary tries (which are, in this case, compressed segment trees). Each interval can be split into around log(M) intervals of lengths equal to powers of 2; each trie includes all numbers in one such interval; also, each index is covered by log(M) of them.
Queries 0 and 2 are adding/removing from these log(M) tries.
Query 3 is just getting the sum of an interval in each trie, just like in a standard segtree.
Query 1 for each trie is moving down that trie; if the vertex that corresponds to taking the next bit opposite to that of x exists, move to it; otherwise, move to the other vertex (it has to exist, because these tries have leaves in depth exactly log(x)).
Query 4 needs moving down tries in parallel - find out how many numbers (in all tries) have 0 as the next bit; if itās less than k, subtract that number from k and take 1 as the next bit of the answer; otherwise, take 0.
I tried implementing this and speeding it up, but only got to around <= 2s. I donāt think I had a chance with this time limitā¦
code shows Access Denied!!
1 Like
i used persistent Trie for this problem. but it still fails the last test case 
. code complexity is M2lgn a t most if only type 3 query ar considered.
http://www.codechef.com/viewsolution/5888271
here is my last submission where code complexity is M*lgn for every query. but still getting tle 
http://www.codechef.com/viewsolution/5888456
i cant figure out how to do type 3 query using the method mentioned in editorialā¦can anyone help?
Authorās and Testerās Solutions are not accessible 
getting WA in tasks: 1,4,5,6,10,11
Can anyone please give any test cases for which my code is falling.
I am following the editorial logic i.e tries.
Thanks
donāt know why we have 5 sec for SEALCM and 1.5 sec for this questionā¦
and java always show TLE for segment tree problemsā¦
all we need to do is to learn c++ ?
i did thatā¦ it think itās simpler as we donāt have to store any list on each node of the trie as in the above solutionā¦just the last inserted index is enough,and also we get O(1) deletionā¦
When getting TLE for the last test case, check your implementation of the XOR query. For the XOR query, you donāt need to count the number of indices between L and R in each node. You only need to know, whether there is at least one. As a result, you donāt need to calculate both lower_bound and upper_bound - only one of them is sufficient (find it and check, whether the value is between L and R). This way, you can reduce number of steps in each node from 2*log(N) to 1*log(N).
1 Like
Is there any standard template for trie?
Thanksā¦Got ACedā¦In fact, time reduced considerably. 
Probably, this problem is best done with persistence.
access denied for all solution files in Jan 2015 editorialsā¦ āThis XML file does not appear to have any style information associated with it. The document tree is shown below.
ā¦ā
Yes i had also used the same approach 
what does ct in your code do ?