RMQ相关的数据结构和算法
Login to join training plan
RMQ（Range Minimum/Maximum Query，区间查询）是一大类问题，变形很多，难度也较大。
绿及以下难度的题必做，蓝及以上难度的题根据自身情况选做。
For more information, please visit RMQ - OI Wiki
-
可以 try 一 try 挑战 P7167 [eJOI2020 Day1] Fountain，《深入浅出·进阶篇》P53有讲解。还可参考洛谷题解，保证你能收获更多有趣解法。
-
做线段树的题目时，一定要先想清楚并设计好该题抽象出来的两个关键信息：节点维护的【值】和相关【标记】。其他需要认真设计的是【标记下放】（pushDown）过程、【区间合并】（pushUp）过程。
Section 1. ST表
Open
| Problem | Tried | AC | Difficulty |
|---|---|---|---|
| P3865 【模板】ST 表 && RMQ 问题 | 86 | 17 | 7 |
| P2880 [USACO07JAN] Balanced Lineup G | 18 | 16 | 5 |
| P252 玉米地 | 35 | 10 | 7 |
| P8818 [CSP-S 2022] 策略游戏 | 11 | 2 | 10 |
| P8773 [蓝桥杯 2022 省 A] 选数异或 | 13 | 1 | 10 |
| P7167 [eJOI2020 Day1] Fountain | 29 | 1 | 10 |
| P7009 [CERC2013] Magical GCD | 33 | 1 | 10 |
Section 2. 树状数组
Open
| Problem | Tried | AC | Difficulty |
|---|---|---|---|
| P3374 【模板】树状数组 1 | 77 | 16 | 7 |
| P3368 【模板】树状数组 2 | 41 | 15 | 6 |
| P3372 【模板】线段树 1 | 125 | 14 | 9 |
| P1908 逆序对 | 48 | 12 | 7 |
| P2068 统计和 | 18 | 7 | 8 |
| P117 「一本通 4.1 例 3」校门外的树 | 7 | 1 | 10 |
| P116 「一本通 4.1 例 2」数星星 Stars | 21 | 4 | 8 |
| P5057 [CQOI2006] 简单题 | 4 | 4 | 10 |
| P2357 守墓人 | 28 | 4 | 9 |
| P5677 [GZOI2017] 配对统计 | 0 | 0 | (None) |
Section 3. 线段树
Open
| Problem | Tried | AC | Difficulty |
|---|---|---|---|
| P3374 【模板】树状数组 1 | 77 | 16 | 7 |
| P3372 【模板】线段树 1 | 125 | 14 | 9 |
| P3870 [TJOI2009] 开关 | 34 | 12 | 6 |
| P3373 【模板】线段树 2 | 69 | 12 | 8 |
| P4588 [TJOI2018] 数学计算 | 54 | 11 | 7 |
| P2023 [AHOI2009] 维护序列 | 14 | 9 | 8 |
| P1438 无聊的数列 | 50 | 8 | 8 |
| P1253 扶苏的问题 | 105 | 6 | 9 |
| P4513 小白逛公园 | 41 | 3 | 9 |
| P2894 [USACO08FEB] Hotel G | 10 | 1 | 10 |
| P1471 方差 | 17 | 3 | 9 |
| P6025 线段树 | 2 | 0 | 10 |
Section 4. 分块
Open
| Problem | Tried | AC | Difficulty |
|---|---|---|---|
| P3372 【模板】线段树 1 | 125 | 14 | 9 |
| P2801 教主的魔法 | 16 | 1 | 10 |
| P7492 [传智杯 #3 决赛] 序列 | 0 | 0 | (None) |
| P11221 [COTS 2019] 序列操作 K-ti | 0 | 0 | (None) |
| P4168 [Violet] 蒲公英 | 37 | 2 | 9 |
| P1903 [国家集训队] 数颜色 / 维护队列 | 0 | 0 | (None) |
