灵神题单/自用

时间久了记不清哪些刷过，哪些未刷过。遂用复选框改造，做题后留痕。

零、常用枚举技巧

§0.1 枚举右，维护左

对于 双变量问题，例如两数之和 ai+aj=ta_i+a_j=tai​+aj​=t，可以枚举右边的 aja_jaj​，转换成 单变量问题，也就是在 aja_jaj​ 左边查找是否有 ai=t−aja_i = t-a_jai​=t−aj​，这可以用哈希表维护。

我把这个技巧叫做 枚举右，维护左。

讲解

• 1. 两数之和
• 1512. 好数对的数目 1161
• 219. 存在重复元素 II
• 121. 买卖股票的最佳时机
• 2815. 数组中的最大数对和 1295
• 2342. 数位和相等数对的最大和 1309
• 1679. K 和数对的最大数目 1346
• 2260. 必须拿起的最小连续卡牌数 1365
• 1010. 总持续时间可被 60 整除的歌曲 1377
• 3185. 构成整天的下标对数目 II 同 1010 题
• 2748. 美丽下标对的数目 非暴力做法
• 2874. 有序三元组中的最大值 II 1583
• 454. 四数相加 II ~1700
• 1014. 最佳观光组合 1730
• 1814. 统计一个数组中好对子的数目 1738
• 2905. 找出满足差值条件的下标 II 1764
• 1031. 两个非重叠子数组的最大和 ~2000 做到 O(n)\mathcal{O}(n)O(n)
• 2555. 两个线段获得的最多奖品 2081
• 3267. 统计近似相等数对 II 2545
• 1214. 查找两棵二叉搜索树之和（会员题）
• 2613. 美数对（会员题）
• 2964. 可被整除的三元组数量（会员题）
• 面试题 16.24. 数对和
• 1534. 统计好三元组
• 1995. 统计特殊四元组

§0.2 枚举中间

对于三个或者四个变量的问题，枚举中间的变量往往更好算。

• 2909. 元素和最小的山形三元组 II 1479
• 1930. 长度为 3 的不同回文子序列 1533
• 3128. 直角三角形 1541
• 2874. 有序三元组中的最大值 II 1583
• 447. 回旋镖的数量
• 3067. 在带权树网络中统计可连接服务器对数目 1909
• 2242. 节点序列的最大得分 2304
• 2867. 统计树中的合法路径数目 2428
• 2552. 统计上升四元组 2433
• 3257. 放三个车的价值之和最大 II 2553
• 3073. 最大递增三元组（会员题）

一、前缀和

§1.1 基础

讲解

• 303. 区域和检索 - 数组不可变
• 2559. 统计范围内的元音字符串数 1435
• 2389. 和有限的最长子序列
• 3152. 特殊数组 II 1523
• 1749. 任意子数组和的绝对值的最大值 1542
• 2438. 二的幂数组中查询范围内的乘积 1610
• 2055. 蜡烛之间的盘子 1819
• 1744. 你能在你最喜欢的那天吃到你最喜欢的糖果吗？ 1859
• 53. 最大子数组和（题解：前缀和做法）

§1.2 前缀和与哈希表

通常要用到「枚举右，维护左」的技巧。

讲解

• 930. 和相同的二元子数组 1592
• 560. 和为 K 的子数组
• 1524. 和为奇数的子数组数目 1611
• 974. 和可被 K 整除的子数组 1676
• 523. 连续的子数组和
• 437. 路径总和 III
• 2588. 统计美丽子数组数目 1697
• 525. 连续数组
• 3026. 最大好子数组和 1817
• 1477. 找两个和为目标值且不重叠的子数组 1851
• 1546. 和为目标值且不重叠的非空子数组的最大数目 1855
• 面试题 17.05. 字母与数字
• 1124. 表现良好的最长时间段 1908
• 2488. 统计中位数为 K 的子数组 1999
• 1590. 使数组和能被 P 整除 2039
• 2845. 统计趣味子数组的数目 2073
• 1442. 形成两个异或相等数组的三元组数目 做到 O(n)\mathcal{O}(n)O(n)
• 2025. 分割数组的最多方案数 2218
• 2949. 统计美丽子字符串 II 2445
• 325. 和等于 k 的最长子数组长度（会员题）
• 548. 将数组分割成和相等的子数组（会员题）
• 1983. 范围和相等的最宽索引对（会员题）
• 2489. 固定比率的子字符串数（会员题）
• 2950. 可整除子串的数量（会员题）

§1.3 距离和

图解

• 1685. 有序数组中差绝对值之和 1496
• 2615. 等值距离和 1793
• 2602. 使数组元素全部相等的最少操作次数 1903
• 2968. 执行操作使频率分数最大 2444
• 1703. 得到连续 K 个 1 的最少相邻交换次数 2467
• 3086. 拾起 K 个 1 需要的最少行动次数 2673

§1.4 前缀异或和

• 1310. 子数组异或查询 1460
• 1177. 构建回文串检测 1848
• 1371. 每个元音包含偶数次的最长子字符串 2041
• 1542. 找出最长的超赞子字符串 2222
• 1915. 最美子字符串的数目 2235
• 2791. 树中可以形成回文的路径数 2677

§1.5 其他一维前缀和

• 1895. 最大的幻方 1781
• 1878. 矩阵中最大的三个菱形和 1898 斜向前缀和
• 1031. 两个非重叠子数组的最大和 做到 O(n)\mathcal{O}(n)O(n)
• 2245. 转角路径的乘积中最多能有几个尾随零 2037
• 1712. 将数组分成三个子数组的方案数 2079
• 1862. 向下取整数对和 2170
• 363. 矩形区域不超过 K 的最大数值和 枚举上下边界转换成一维
• 2281. 巫师的总力量和 2621
• 2983. 回文串重新排列查询 2780
• 2955. 同端子串的数量（会员题）
• 1788. 最大化花园的美观度（会员题）
• 2819. 购买巧克力后的最小相对损失（会员题）

§1.6 二维前缀和

【图解】一张图秒懂二维前缀和！

• 304. 二维区域和检索 - 矩阵不可变
• 1314. 矩阵区域和 1484
• 3070. 元素和小于等于 k 的子矩阵的数目 1499
• 1738. 找出第 K 大的异或坐标值 1671
• 3212. 统计 X 和 Y 频数相等的子矩阵数量 1673
• 1292. 元素和小于等于阈值的正方形的最大边长 1735
• 221. 最大正方形
• 1277. 统计全为 1 的正方形子矩阵
• 1504. 统计全 1 子矩形 1845
• 1074. 元素和为目标值的子矩阵数量 2189

二维前缀最小值：

• 3148. 矩阵中的最大得分 1820

二、差分

§2.1 一维差分（扫描线）

原理讲解（推荐和【图解】从一维差分到二维差分 一起看）

• 2848. 与车相交的点 1230
• 1893. 检查是否区域内所有整数都被覆盖 1307
• 1854. 人口最多的年份 1370
• 2960. 统计已测试设备
• 1094. 拼车 1441
• 1109. 航班预订统计 1570
• 56. 合并区间
• 57. 插入区间
• 732. 我的日程安排表 III
• 2406. 将区间分为最少组数 1713
• 2381. 字母移位 II 1793
• 995. K 连续位的最小翻转次数 1835
• 1589. 所有排列中的最大和 1871
• 1526. 形成目标数组的子数组最少增加次数 1872
• 1943. 描述绘画结果 1969
• 3224. 使差值相等的最少数组改动次数 1996 做法不止一种
• 2251. 花期内花的数目 2022
• 2772. 使数组中的所有元素都等于零 2029
• 3229. 使数组等于目标数组所需的最少操作次数 2067
• 798. 得分最高的最小轮调 2130
• 2528. 最大化城市的最小供电站数目 2236
• 1674. 使数组互补的最少操作次数 2333
• 3017. 按距离统计房屋对数目 II 2709
• 253. 会议室 II（会员题）
• 370. 区间加法（会员题）
• 1989. 捉迷藏中可捕获的最大人数（会员题）
• 759. 员工空闲时间（会员题）
• 2021. 街上最亮的位置（会员题）
• 2015. 每段建筑物的平均高度（会员题）
• 2237. 计算街道上满足所需亮度的位置数量（会员题）
• 3009. 折线图上的最大交点数量（会员题）
• 3279. 活塞占据的最大总面积（会员题）

§2.2 二维差分

【图解】从一维差分到二维差分

• 2536. 子矩阵元素加 1 1583
• 850. 矩形面积 II 2236
• 2132. 用邮票贴满网格图 2364
• LCP 74. 最强祝福力场

三、栈

§3.1 基础

• 1441. 用栈操作构建数组 1180
• 844. 比较含退格的字符串 1228
• 682. 棒球比赛
• 2390. 从字符串中移除星号 1348
• 1472. 设计浏览器历史记录 1454
• 946. 验证栈序列 1462
• 71. 简化路径

§3.2 进阶

• 3170. 删除星号以后字典序最小的字符串 1772
• 155. 最小栈
• 1381. 设计一个支持增量操作的栈
• 636. 函数的独占时间
• 2434. 使用机器人打印字典序最小的字符串 1953
• 895. 最大频率栈 2028
• 1172. 餐盘栈 2110
• 2589. 完成所有任务的最少时间 2381 做法不止一种
• 716. 最大栈（会员题）

§3.3 邻项消除

• 2696. 删除子串后的字符串最小长度 1282
• 1047. 删除字符串中的所有相邻重复项 1286
• 1544. 整理字符串 1344
• 1003. 检查替换后的词是否有效 1427
• 2216. 美化数组的最少删除数 1510
• 1209. 删除字符串中的所有相邻重复项 II 1542
• 2211. 统计道路上的碰撞次数 1581
• 735. 小行星碰撞
• 1717. 删除子字符串的最大得分 1868
• 2197. 替换数组中的非互质数 2057
• 2751. 机器人碰撞 2092

§3.4 合法括号字符串

注：部分题目可以不用栈，而是用一个数字记录嵌套深度。

• 20. 有效的括号
• 921. 使括号有效的最少添加 1242
• 1021. 删除最外层的括号 1311
• 1614. 括号的最大嵌套深度 1323
• 1190. 反转每对括号间的子串 1486
• 856. 括号的分数 1563
• 1249. 移除无效的括号 1657
• 1963. 使字符串平衡的最小交换次数 1689
• 678. 有效的括号字符串 ~1700
• 32. 最长有效括号
• 1111. 有效括号的嵌套深度 1749
• 1541. 平衡括号字符串的最少插入次数 1759
• 2116. 判断一个括号字符串是否有效 2038

§3.5 表达式解析

• 150. 逆波兰表达式求值
• 1006. 笨阶乘 1408
• 224. 基本计算器
• 227. 基本计算器 II
• 726. 原子的数量
• 1106. 解析布尔表达式 1880
• 591. 标签验证器
• 736. Lisp 语法解析
• 1096. 花括号展开 II 2349
• 1896. 反转表达式值的最少操作次数 2532
• 770. 基本计算器 IV 2863
• 439. 三元表达式解析器（会员题）
• 772. 基本计算器 III（会员题）
• 1087. 花括号展开（会员题）
• 1597. 根据中缀表达式构造二叉表达式树（会员题）
• 1628. 设计带解析函数的表达式树（会员题）

§3.6 对顶栈

• 2296. 设计一个文本编辑器 1912

§3.7 单调栈

见 单调栈题单。

四、队列

队列常用在 BFS 中，见 网格图题单 和 图论题单。与此相比，栈常用在 DFS 中，但无需我们手动维护。

§4.1 基础

• 933. 最近的请求次数 1338
• 950. 按递增顺序显示卡牌 1686
• 649. Dota2 参议院
• 346. 数据流中的移动平均值（会员题）
• 362. 敲击计数器（会员题）
• 379. 电话目录管理系统（会员题）
• 1429. 第一个唯一数字（会员题）
• 2534. 通过门的时间（会员题）

§4.2 设计

• 225. 用队列实现栈
• 232. 用栈实现队列
• 622. 设计循环队列
• 641. 设计循环双端队列
• 1670. 设计前中后队列 1610

§4.3 双端队列

• 2810. 故障键盘 做到 O(n)\mathcal{O}(n)O(n)

§4.4 单调队列

个人觉得叫单调双端队列更准确。

原理讲解

• 239. 滑动窗口最大值
• LCR 184. 设计自助结算系统
• 1438. 绝对差不超过限制的最长连续子数组 1672
• 2398. 预算内的最多机器人数目 1917
• 862. 和至少为 K 的最短子数组 2307
• 1499. 满足不等式的最大值 2456
• 2071. 你可以安排的最多任务数目 2648

§4.5 单调队列优化 DP

一般用来维护一段转移来源的最值。

1. 前提：区间右端点变大时，左端点也在变大（同滑动窗口）。
2. 转移前，去掉队首无用数据。
3. 计算转移（直接从队首转移）。
4. 把数据（一般是 f[i]f[i]f[i]）插入队尾前，去掉队尾无用数据。

• 2944. 购买水果需要的最少金币数 1709 可以用单调队列优化到 O(n)\mathcal{O}(n)O(n)
• 1696. 跳跃游戏 VI 1954
• 1425. 带限制的子序列和 2032
• 375. 猜数字大小 II 可以用单调队列优化到 O(n2)\mathcal{O}(n^2)O(n2)
• 1687. 从仓库到码头运输箱子 2610
• 3117. 划分数组得到最小的值之和 2735
• 2945. 找到最大非递减数组的长度 2943
• 2969. 购买水果需要的最少金币数 II（会员题）

五、堆（优先队列）

§5.1 基础

• 1046. 最后一块石头的重量 1173
• 3264. K 次乘运算后的最终数组 I 1178
• 2558. 从数量最多的堆取走礼物 1277
• 2336. 无限集中的最小数字 1375
• 2530. 执行 K 次操作后的最大分数 1386
• 3066. 超过阈值的最少操作数 II 1400
• 1962. 移除石子使总数最小 1419
• 3275. 第 K 近障碍物查询 1420 维护前 kkk 小
• 1845. 座位预约管理系统 1429 你能做到复杂度和 nnn 无关吗？
• 2208. 将数组和减半的最少操作次数 1550
• 2233. K 次增加后的最大乘积 1686
• 3296. 移山所需的最少秒数 1695
• 1942. 最小未被占据椅子的编号 1695
• 1801. 积压订单中的订单总数 1711
• 2406. 将区间分为最少组数 1713
• 2462. 雇佣 K 位工人的总代价 1764
• 1834. 单线程 CPU 1798
• 1792. 最大平均通过率 1818
• 2931. 购买物品的最大开销 1822
• 1882. 使用服务器处理任务 1979
• 2402. 会议室 III 2093
• 253. 会议室 II（会员题）
• 1167. 连接木棍的最低费用（会员题）

§5.2 进阶

• 23. 合并 K 个升序链表
• 355. 设计推特
• 502. IPO
• 1705. 吃苹果的最大数目 1930
• 778. 水位上升的泳池中游泳
• 1631. 最小体力消耗路径 1948
• 1354. 多次求和构造目标数组 2015
• 1353. 最多可以参加的会议数目 2016
• 1235. 规划兼职工作 2023 也可以 DP
• 632. 最小区间
• 2542. 最大子序列的分数 2056
• 1383. 最大的团队表现值 2091
• 2503. 矩阵查询可获得的最大分数 2196
• 2163. 删除元素后和的最小差值 2225
• 857. 雇佣 K 名工人的最低成本 2260
• 1606. 找到处理最多请求的服务器 2276
• 1851. 包含每个查询的最小区间 2286
• 218. 天际线问题
• 407. 接雨水 II
• 2940. 找到 Alice 和 Bob 可以相遇的建筑 2327
• 2589. 完成所有任务的最少时间 2381 做法不止一种
• 3266. K 次乘运算后的最终数组 II 2509
• 1675. 数组的最小偏移量 2533
• 2617. 网格图中最少访问的格子数 2582
• 2532. 过桥的时间 2589
• LCP 33. 蓄水 思考：更快的做法
• 1199. 建造街区的最短时间（会员题）

§5.3 重排元素

• 984. 不含 AAA 或 BBB 的字符串 1474 不需要堆，选这题的目的是引入贪心思想
• 767. 重构字符串 1681
• 1054. 距离相等的条形码 1702
• 1953. 你可以工作的最大周数 1804
• 1405. 最长快乐字符串 1821
• 3081. 替换字符串中的问号使分数最小 1905
• 621. 任务调度器
• 358. K 距离间隔重排字符串（会员题）

§5.4 第 K 小/大

部分题目也可以用二分解决。

• 264. 丑数 II
• 378. 有序矩阵中第 K 小的元素
• 373. 查找和最小的 K 对数字
• 1439. 有序矩阵中的第 k 个最小数组和 2134
• 786. 第 K 个最小的质数分数 2169
• 2386. 找出数组的第 K 大和 2648

§5.5 反悔堆

基于堆的反悔贪心。

• LCP 30. 魔塔游戏
• 1642. 可以到达的最远建筑 1962
• 630. 课程表 III
• 871. 最低加油次数 2074
• 2813. 子序列最大优雅度 2582 也可以不用堆
• 3049. 标记所有下标的最早秒数 II 3111
• 2599. 使前缀和数组非负（会员题）

§5.6 懒删除堆

• 2349. 设计数字容器系统 1540
• 2353. 设计食物评分系统 1782
• 3092. 最高频率的 ID 1793
• 2034. 股票价格波动 1832
• 1172. 餐盘栈 2110

§5.7 对顶堆（滑动窗口第 K 小/大）

也可以用有序集合。

• 2102. 序列顺序查询 2159
• 295. 数据流的中位数
• 480. 滑动窗口中位数
• 703. 数据流中的第 K 大元素
• 1825. 求出 MK 平均值 2396
• 3013. 将数组分成最小总代价的子数组 II 2540
• 3321. 计算子数组的 x-sum II ~2550
• LCP 24. 数字游戏

另见 图论题单 中的 Dijkstra 算法。

六、字典树（trie）

§6.1 基础

• 208. 实现 Trie (前缀树)
• 211. 添加与搜索单词 - 数据结构设计
• 14. 最长公共前缀
• 648. 单词替换
• 677. 键值映射
• 720. 词典中最长的单词
• 1268. 搜索推荐系统 1573
• 1233. 删除子文件夹
• 820. 单词的压缩编码 1632
• 2416. 字符串的前缀分数和 1725
• 2261. 含最多 K 个可整除元素的子数组 做到 O(n2)\mathcal{O}(n^2)O(n2)
• 1804. 实现 Trie （前缀树） II（会员题）
• 2168. 每个数字的频率都相同的独特子字符串的数量（会员题）同 2261 题

§6.2 进阶

• 676. 实现一个魔法字典
• 212. 单词搜索 II
• 336. 回文对
• 745. 前缀和后缀搜索
• 3093. 最长公共后缀查询 2118
• 3045. 统计前后缀下标对 II 2328
• 1948. 删除系统中的重复文件夹 2534
• 425. 单词方块（会员题）
• 527. 单词缩写（会员题）
• 588. 设计内存文件系统（会员题）
• 616. 给字符串添加加粗标签（会员题）
• 758. 字符串中的加粗单词（会员题）
• 642. 设计搜索自动补全系统（会员题）
• 1065. 字符串的索引对（会员题）
• 1166. 设计文件系统（会员题）
• 1858. 包含所有前缀的最长单词（会员题）

§6.3 字典树优化 DP

• 139. 单词拆分
• 140. 单词拆分 II
• 面试题 17.13. 恢复空格
• 472. 连接词 ~2300
• 2977. 转换字符串的最小成本 II 2696

§6.4 0-1 字典树（异或字典树）

部分题目也可以用试填法解决。

• 421. 数组中两个数的最大异或值 ~2000
• 2935. 找出强数对的最大异或值 II 2349
• 1707. 与数组中元素的最大异或值 2359
• 1803. 统计异或值在范围内的数对有多少 2479
• 1938. 查询最大基因差 2503
• 2479. 两个不重叠子树的最大异或值（会员题）

七、并查集

§7.1 基础

见 网格图题单 中的 DFS 和 图论题单 中的 DFS，其中大部分题目也可以用并查集实现。

• 990. 等式方程的可满足性 1638
• 721. 账户合并
• 737. 句子相似性 II（会员题）
• 1101. 彼此熟识的最早时间（会员题）
• 1258. 近义词句子（会员题）

§7.2 进阶

• 1202. 交换字符串中的元素 1855
• 1061. 按字典序排列最小的等效字符串
• 1722. 执行交换操作后的最小汉明距离 1892
• 765. 情侣牵手 1999
• 684. 冗余连接 做法不止一种
• 685. 冗余连接 II
• 947. 移除最多的同行或同列石头 2035
• 839. 相似字符串组 2054
• 1970. 你能穿过矩阵的最后一天 2124
• 2076. 处理含限制条件的好友请求 2131
• 1579. 保证图可完全遍历 2132
• 959. 由斜杠划分区域 2136
• 2812. 找出最安全路径 2154
• 2503. 矩阵查询可获得的最大分数 2196
• 2867. 统计树中的合法路径数目 2428
• 2421. 好路径的数目 2445
• 2157. 字符串分组 2499
• 1632. 矩阵转换后的秩 2530
• 803. 打砖块 2765
• 1569. 将子数组重新排序得到同一个二叉搜索树的方案数 思考：更快的做法
• 3235. 判断矩形的两个角落是否可达
• LCP 71. 集水器
• 2371. 最小化网格中的最大值（会员题）
• 2459. 通过移动项目到空白区域来排序数组（会员题）置换

§7.3 公因数并查集

也叫 GCD 并查集。

• 2709. 最大公约数遍历 2172
• 1627. 带阈值的图连通性 2221
• 952. 按公因数计算最大组件大小 2272
• 1998. 数组的最大公因数排序 2429

§7.4 数组上的并查集

• 1562. 查找大小为 M 的最新分组 1928
• 1488. 避免洪水泛滥 1974
• 2382. 删除操作后的最大子段和 2136
• 2334. 元素值大于变化阈值的子数组 2381

§7.5 区间并查集

• 1851. 包含每个查询的最小区间 2286
• 3244. 新增道路查询后的最短距离 II 2270
• 2158. 每天绘制新区域的数量（会员题）

§7.6 边权并查集

• 399. 除法求值
• 2307. 检查方程中的矛盾之处（会员题）

八、树状数组和线段树

能用树状数组解决的题目，也能用线段树解决（反过来不一定）。但树状数组实现简单，代码短。

为方便大家练习，我把适合用树状数组解决的题目分到树状数组中，其余分到线段树中。

§8.1 树状数组

讲解：带你发明树状数组！附数学证明

• 307. 区域和检索 - 数组可修改
• 3072. 将元素分配到两个数组中 II 2053
• 3187. 数组中的峰值 2154
• 1649. 通过指令创建有序数组 2208
• 1626. 无矛盾的最佳球队
• 1409. 查询带键的排列
• 2250. 统计包含每个点的矩形数目
• 2179. 统计数组中好三元组数目 2272
• 1395. 统计作战单位数
• 2659. 将数组清空 2282
• 2653. 滑动子数组的美丽值 树状数组二分
• 1505. 最多 K 次交换相邻数位后得到的最小整数 2337
• 2926. 平衡子序列的最大和 2448
• 2736. 最大和查询 2533
• 3245. 交替组 III 3112 环形数组
• 1756. 设计最近使用（MRU）队列（会员题）
• 2519. 统计 K-Big 索引的数量（会员题）
• 2613. 美数对（会员题）曼哈顿最近点对
• 2921. 价格递增的最大利润三元组 II（会员题）
• 308. 二维区域和检索 - 可变（会员题）

§8.2 逆序对

除了可以用树状数组解决，部分题目也可以在归并排序的同时计算。

• LCR 170. 交易逆序对的总数
• 315. 计算右侧小于当前元素的个数
• 493. 翻转对
• 327. 区间和的个数
• 2426. 满足不等式的数对数目 2030
• 1850. 邻位交换的最小次数
• 2193. 得到回文串的最少操作次数 做到 O(nlog⁡n)\mathcal{O}(n\log n)O(nlogn)
• 1885. 统计数对（会员题）

§8.3 线段树（无区间更新）

• 1157. 子数组中占绝大多数的元素 2205
• 2407. 最长递增子序列 II 2280
• 2940. 找到 Alice 和 Bob 可以相遇的建筑 2327 线段树二分
• 2286. 以组为单位订音乐会的门票 2470 线段树二分
• 3161. 物块放置查询 2513
• 2213. 由单个字符重复的最长子字符串 2629
• 3165. 不包含相邻元素的子序列的最大和 2697
• LCP 81. 与非的谜题

§8.4 Lazy 线段树（有区间更新）

• 2589. 完成所有任务的最少时间 2381
• 2569. 更新数组后处理求和查询 2398
• 1622. 奇妙序列 2476 有更简单的做法
• 2916. 子数组不同元素数目的平方和 II 2816
• LCP 05. 发 LeetCoin
• LCP 27. 黑盒光线反射

§8.5 动态开点线段树

部分题目也可以用珂朵莉树解决。

• 699. 掉落的方块
• 715. Range 模块
• 729. 我的日程安排表 I
• 731. 我的日程安排表 II
• 732. 我的日程安排表 III
• 850. 矩形面积 II
• 2276. 统计区间中的整数数目 2222
• 2770. 达到末尾下标所需的最大跳跃次数

专题：离线算法

对询问排序，通过改变回答询问的顺序，使问题更容易处理。

相应的，在线算法就是按照 queries\textit{queries}queries 的顺序一个一个处理。

• 2343. 裁剪数字后查询第 K 小的数字 1652
• 2070. 每一个查询的最大美丽值 1724
• 1847. 最近的房间 2082
• 2503. 矩阵查询可获得的最大分数 2196
• 1851. 包含每个查询的最小区间 2286
• 1697. 检查边长度限制的路径是否存在 2300
• 2940. 找到 Alice 和 Bob 可以相遇的建筑 2327
• 2747. 统计没有收到请求的服务器数目 2405
• 1938. 查询最大基因差 2503
• 2736. 最大和查询 2533

关联题单

• 关于链表和二叉树的题目，见 链表、二叉树与一般树。
• 关于其他字符串算法，见 字符串题单。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/最短路/最小生成树/二分图/基环树/欧拉路径）
7. 动态规划（入门/背包/状态机/划分/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、二叉树与一般树（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

如果你发现有题目可以补充进来，欢迎评论反馈。

在线工具

• HTML 转 Markdown
• 字符串替换