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 ?