i used persistent segment tree to solve this problem. my code complexity is M*lgn. but it still gets tle in the last test case :’( if anyone can point to any optimization it would be very helpful 
http://www.codechef.com/viewsolution/5888456
You can make it without using pointers, which are very slow.Once you need a new node in your trie(I see they are persistent segment trie in your solution), you just make something like nr ++, and nr is going to be the new node, or if you want, A[nr], where A is a structure that remebears what you need.
I am unable to open your solution for some reason.
Here is my persistent segment tree solution using pointers with a full AC. 
Maybe you can figure out a way to optimize your solution from that.
Good luck!