Cards shuffing (SPOJ 4390)

https://www.spoj.pl/problems/CARDSHUF/

問題

[1,N]までの数列に対して、i番目の数値をj番目に移動するという操作をM回繰り返す。最終的にできた数列を元の数列に戻すのに何回操作を行わないといけないか答えよ。
1<=N,M<=100,000

解法

平衡二分木でO(logN)で操作を行い最後の数列を作る。最後の数列から最初の数列に戻すのに必要な操作の回数は N-最長増加部分列の長さ なのでこれをO(NlogN)で計算してやれば良い。
TLEが異常に厳しいので平衡二分木の高速化が必要。具体的にやった高速化は、randをXorシフトに変更、Splitを使わないEraseにした、最初の数列を完全二分木で作ってやったなど。