T3 线段树 $\Theta(n \log n)$，2e6，六倍常数，一秒。$n \le 2000$ 写了 $n$ 个 2e5 的 memset，过了。

开香槟一看 T2 挂成 50pts 了。