算法思想·多选训练7

第 1 题（多选）

关于莫队算法，正确的有（）。

{{ multiselect(1) }}

• 适用于所有最短路问题
• 通过移动左右端点维护答案
• 通常离线重排询问
• 是在线算法不能排序询问

第 2 题（多选）

关于 FFT/NTT，正确的有（）。

{{ multiselect(2) }}

• 可加速多项式卷积
• NTT 在合适模数下避免浮点误差
• FFT 是单源最短路算法
• NTT 不需要模数条件

第 3 题（多选）

关于平面最近点对分治，正确的有（）。

{{ multiselect(3) }}

• 需要按坐标排序和处理跨分界候选
• 必须枚举所有点对
• 只能用于 n<=10
• 经典复杂度可达 O(n log n)

第 4 题（多选）

关于主席树求静态区间第 k 小，正确的有（）。

{{ multiselect(4) }}

• 每次查询必须重建整棵树
• 不能处理离散化后的值域
• 通常建立前缀版本
• 查询 [l,r] 可用 version[r] 与 version[l-1] 相减

第 5 题（多选）

关于后缀数组，正确的有（）。

{{ multiselect(5) }}

• sa 表示后缀字典序排名对应的起点
• height/LCP 常记录相邻排名后缀的最长公共前缀
• 只能处理回文串
• 不能与 RMQ 结合