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!