针对于本题而言个人认为线段树也是不错的解法之一，并且 $n\log n$ 的做法也并不会被卡常数，提交记录。

并且注意，这里使用的输入输出是没有关闭同步流的 cin 和 cout，关闭同步流后甚至可以到达 500ms 左右，提交记录。

线段树的板子难度在绿，但是查找标签的时候也可以看到黄色的线段树标签。

故申请添加标签：线段树。

欢迎讨论。