1. 尽量让内存连续访问，也就是说二维数组 $f[i][j]$ 枚举的时候按照 $j$ 升序枚举。

2. 可以试着用值域分块，这样询问的常数就会小很多。

3. 归并排序那里可以在存放右数组时进行归并排序，可以小一半常数。

4. 加个快速输出。

如果你发现你块长越大跑得越慢，可能是你有的地方可以写成 $O(nB)$ 的写成了 $O(\dfrac{n^2}{B})$，前者在本题中表现应该会比较优秀。