算法思想·多选训练6

第 1 题（多选）

关于离散化，正确的有（）。

{{ multiselect(1) }}

• 常配合树状数组或线段树
• 必须保留原始差值大小才可比较
• 可压缩大值域
• 保留相对大小关系

第 2 题（多选）

关于扫描线，正确的有（）。

{{ multiselect(2) }}

• 只能用于一维前缀和
• 不能处理矩形面积并
• 常配合线段树维护覆盖长度
• 常配合离散化

第 3 题（多选）

关于点分治，正确的有（）。

{{ multiselect(3) }}

• 常选树的重心作为分治中心
• 常用于统计树上路径信息
• 每层一定只处理一个叶子
• 用于一般有向图强连通分量

第 4 题（多选）

关于虚树，正确的有（）。

{{ multiselect(4) }}

• 通常保留关键点及必要 LCA
• 一定包含原树所有点
• 边权常为原树距离
• 只适合完全图

第 5 题（多选）

关于 CDQ 分治，正确的有（）。

{{ multiselect(5) }}

• 常与 BIT 结合处理偏序
• 只能用于字符串匹配
• 不允许递归
• 常处理离线贡献