Lucky Palindrome of November LunchTime

I am doing Lucky Palindrome question of November Lunch.

I passed it for two sub task but then getting TLE.

Editorial says we should use treap for remaining sub tasks.

Here is the link for the editorial

I would be very thankful if somebody can please explain me how to use treap in this question.

I know what is treap but don’t know how to use it here.

Thank you.


Can you please post the link to Editorial

I have posted the link, but it explains nothing about how to use treap.