需要的前置技能

• 线段树（权值线段树）
• 离散化

常见应用

• 区间/树上路径第 K 大
• 区间不同数的个数

所需基础

计算几何 - 凸包、了解 Graham's Scan 算法及其极角序实现。

概述

Graham's Scan 算法的水平序实现是不同于「极角序」的另一种实现方式，它将平面点集按照水平序排序，即按 y 坐标排序，相同时再按 x 坐标排序，之后进行扫描来求得凸包。