线段树套Splay的卡常看这里！

rt。o2属于必备，不在讨论范围内。

1、不要在每个splay里面加入极大值与极小值，这会极大增加你在线段树下层区间的查询运算量。改为特判是否为空即可。（优化约500ms）

2、二分查找时区间初始不要为【0,1e8】。改为当前输入数据的最小值和最大值，可以不严格维护，每次输入数据时取min与max即可。（优化约300ms）

3、尽可能多的用三目运算符代替if else。（优化约10ms）

4、更加优秀的快读（如fread）。（能比getchar快约100ms）

5、编译语言用c++11。（玄学优化，可能会快10ms）

本人代码#2 TLE（2s19），在上述优化后达到了1s60