Ordinary Work

# 对数据结构的爱❤  「所以说，小雪的未来是由乃的~」 算是给水平较低的选手过渡使用的题单，部分章节可能相对简单/经典的练习题没有放上来，算是继承一点学长的意志吧。 # 快捷键 编排可能有一点出入。 [Part I](https://www.luogu.com.cn/training/623296) [Part II](https://www.luogu.com.cn/training/623307) [Part III](https://www.luogu.com.cn/training/623314) [Part IV](https://www.luogu.com.cn/training/623319) # 根号杂选 注意序列分块、操作分块、根号分治三种技巧。 - CF1129D - P3712 少女与战车 - P7811 [JRKSJ R2] 你的名字。 - P5356 [Ynoi2017\] 由乃打扑克 - P4117 [Ynoi2018] 五彩斑斓的世界 - P6578 [Ynoi2019] 魔法少女网站 - P4119 [Ynoi2018] 未来日记 - P6466 分散层叠算法(Fractional Cascading) - CF1491H - CF840E - P5611 [Ynoi2013] D2T2 - P8353 [SDOI/SXOI2022] 无处存储 - P9136 [THUPC 2023 初赛] 种苹果 - P6778 [Ynoi2009] rpdq # 凸包相关 分析单调性往往可以得到更可做的复杂度。 - P4192 旅行规划 - CF436F - P4118 [Ynoi2018] 末日时在做什么？有没有空？可以来拯救吗？ - The 1st Universal Cup. Stage 2: Hong Kong D - ICPC Nanjing 2022 H - ICPC Jinan2023 D - P3309 [SDOI2014] 向量集 - P7164 [COCI2020-2021#1] 3D Histogram # 莫队 做的题都比较少，放一点典的上来。 注意回滚莫队和链表的结合，普通莫队求众数的方法。 - P5398 [Ynoi2018] GOSICK - P5386 [Cnoi2019] 数字游戏 - P9337 [Ynoi2001] 冷たい部屋、一人 - P8530 [Ynoi2003] 博丽灵梦 - P7448 [Ynoi2007] rdiq # 树套树 毫无技巧可言，暴力战斗爽！ - P4632 [APIO2018] 新家 - P5445 [APIO2019] 路灯 - CF1523G # 线段树相关 ## 线段树合并 主要介绍整体 DP 有关的技巧，登山可以使用其他更加好写的方法。 - CF671D - CF1455G - P7422 「PMOI-2」城市 - P5298 [PKUWC2018] Minimax - P6773 [NOI2020] 命运 - P10789 [NOI2024] 登山 ## 线段树维护单调栈 算是被普及的想法之一吧，考虑维护儿子之间的信息，方便计算前缀信息。有兴趣的可以看小粉兔的解析。 - P4198 楼房重建 - CF671E - CodeChef - COT5 Count on a Treap - CF1340F - P4425 [HNOI/AHOI2018] 转盘 - PKUSC2024 D2T3 ## 势能线段树 算是比较正论的分析？ - Loj#6029. 「雅礼集训 2017 Day1」市场 - Uoj#228 基础数据结构练习题 - P7492 [传智杯 #3 决赛] 序列 - P9989 [Ynoi Easy Round 2023] TEST_69 - Loj#6507. 「雅礼集训 2018 Day7」A ## SegBeats 有兴趣可以了解一下区间历史最值和。 - CF793F - CF855F - CF1572F - Uoj#515. 【UR #19】前进四 （转置扫描线） ## Kinetic Tournament Tree 无敌的轮椅数据结构，非常好用。 - CF1178G - P5693 EI 的第六分块 - P6792 [SNOI2020] 区间和 - CF1868F - P9288 [ROI 2018] Innophone - P8987 [北大集训 2021] 简单数据结构 - P5073 [Ynoi2015] 世上最幸福的女孩 ## 历史标记相关 你想要更强劲的力量吗？ 用来加强扫描线功能的技巧，如果想要更加深入，建议学习矩阵知识。 - P4314 CPU 监控 - CF1824D - P3246 [HNOI2016] 序列 - P8868 [NOIP2022] 比赛 - SP1557 GSS2 - Can you answer these queries II - Uoj#164. 【清华集训2015】V - Uoj#169. 【UR #11】元旦老人与数列 - P9990 [Ynoi Easy Round 2023] TEST_90 - LOJ#3033. 「JOISC 2019 Day2」两个天线 （大炮打蚊子） - CF1787I（勉强可以通过） ## 可持久化线段树的区间操作 与李煜东所讲述的事实有一点出入，其实可持久化线段树是可以 pushdown。 - SP11470 to the moon - Uoj#218. 【UNR #1】火车管理 - P7671 [GDOI2016] 疯狂动物城 ## 线段树上维护双指针 这方面的题确实做的少了，非常清新且有趣的 idea。 - P9530 [JOISC2022] 鱼 2 - P5609 对数据结构的爱 ## 线段树分治 其实可以维护序列轴，只是很多人喜欢用来维护时间轴。 - P9168 [省选联考 2023] 人员调度 - P7470 [NOI Online 2021 提高组] 岛屿探险 - P10611 故事结局 ## 猫树分治 题给少了。 - P6240 好吃的题目 - P6109 [Ynoi2009] rprmq1 - CF232E - UOJ#749 [UNR #6]稳健型选手 # 扫描线模型 朴素且大气的结构，写分治的都是懦夫！ - P7530 [USACO21OPEN] United Cows of Farmer John P - Atcoder-dp-w Intervals - P8476 「GLR-R3」惊蛰 - P6406 [COCI2014-2015#2\] Norma - CF1083D - CF1609F - CF1677E - CF1887D - P6292 区间本质不同子串个数 - P9340 [JOISC 2023 Day3] Tourism - P4747 [CERC2017] Intrinsic Interval # LCT 其实意料之外地好写！最后几个 CF 题真的很喜欢所以标全了标题！蜀道难就不放了。 - Uoj#27 共价大爷游长沙 - P3979 遥远的国度 - P4319 变化的道路 - CF916E （值得学习） - P5385 [Cnoi2019] 须臾幻境 - P4764 [CERC2014] Pork barrel - P5489 EntropyIncreaser 与 动态图 - P3703 [SDOI2017] 树点涂色（Access 维护信息的引入） - P9598 [JOI Open 2018] 山体滑坡 - P8531 [Ynoi2003] 戌亥彗星 - P5526 [Ynoi2012] 惊惶的 SCOI2016 - P5649 Sone1 - CF1344E Train Tracks - CF1109F Sasha and Algorithm of Silence's Sounds - CF1137F Matches Are Not a Child's Play # 全局平衡二叉树 名将，有能！ - P4751 【模板】"动态DP"&动态树分治（加强版） - P4211 [LNOI2014] LCA - P5115 Check,Check,Check one two! - CF1208H Red Blue Tree # 分治结构 ## CDQ 分治 我不喜欢。 - P3364 Cool loves touli - P4390 [BalkanOI2007] Mokia 摩基亚 - P3658 [USACO17FEB] Why Did the Cow Cross the Road III P - P4690 [Ynoi2016] 镜中的昆虫 ## 整体二分 我先不放了，可以看一看那些保序回归的题。 ## 点分治 比较轮椅的分治结构。 - P3241 [HNOI2015] 开店 - CF342E Xenia and Tree - P5311 [Ynoi2011] 成都七中 - AT_cf17_final_j Tree MST - P6199 [EER1] 河童重工 - P9260 [PA 2022] Miny - *Shenyang Regional 2022 G. Meet in the Middle ## 边分治 战斗，爽！ - CF757G Can Bash Save the Day? - P4565 [CTSC2018] 暴力写挂 - CF1019E Raining season ## HLD & Dsu on tree 小常数的树上静态链分治。 - FJWC2020 Day3 C - P5161 WD与数列 - P6556 The Forest - P7279 光棱碎片 - P5391 [Cnoi2019] 青染之心 ## 长链剖分 有一堆模板题，令我印象最深的是： - CF526G - CF150E Freezing with Style - P4292 [WC2010] 重建计划 ## 笛卡尔树 简练且有用的最值结构，虽仅有空拳，亦可赛艇！ - P4755 Beautiful Pair - P6881 [JOI 2020 Final] 火事 - P5044 [IOI2018] meetings 会议 - P7219 「JOISC2020」 星座 3 - P5979 [PA2014] Druzyny # 一些黑盒 ## 虚树 非常好用的无敌黑盒，这里放一点和字符串相关的。 - P8571 [JRKSJ R6] Dedicatus545 - P8147 [JRKSJ R4] Salieri ## 半平面数点 - UOJ#553. 【UNR #4】己酸集合 - P8529 [Ynoi2003] 赫露艾斯塔 - P8261 CTS2022 袜子 # KDT 它简直就是战神！ - P4848 崂山白花蛇草水 - P6349 [PA2011] Kangaroos - P6783 [Ynoi2008] rrusq # Tricks ## 一些杂题 比较 trivial。 - CF1422F - P8990 [北大集训 2021] 小明的树 - Uoj#637. 【美团杯2021】A. 数据结构 - P7560 [JOISC 2021 Day1] フードコート - P5439 【XR-2】永恒 - P9335 [Ynoi2001] 雪に咲く花 - P9596 [JOI Open 2018] 冒泡排序 2 - CF1801G A task for substrings - P2305 [NOI2014] 购票 - P10833 [COTS/CETS 2023] 下 Niz - CF983D - P7712 [Ynoi2077] hlcpq - CF1270H Number of Components - CF1336F Journey - 「LibreOJ Round #6」花火（重要技巧！！） ## 颜色段均摊 方便好用的操作。 - CF453E - CF1732E - P7582 「RdOI R2」风雨 - P5576 [CmdOI2019] 口头禅 - P10081 [GDKOI2024 提高组] 新本格魔法少女 - CF1148H Holy Diver ## 减半警报器 喜欢我的鬼街吗？ - Codeforces GYM 102452 I - Codeforces GYM 102331 F - P7603 [THUPC2021] 鬼街 - CCPC2022 绵阳. Call Me Call Me - P10787 [NOI2024] 树的定向 ## 支配点对 优美。 - CF765F Souvenirs - CodeChef MINXORSEG - P7880 [Ynoi2006] rldcot - P8528 [Ynoi2003] 铃原露露 - P9058 [Ynoi2004] rpmtdq - ICPC2023 Xi'an I - GYM102596L Yosupo's Algorithm - P10882 [JRKSJ R9] ZYPRESSEN - P9062 [Ynoi2002] Adaptive Hsearch&Lsearch ## 值域倍增分块 全是典的，没有资源/kk - CF702F T-shirts - P7447 [Ynoi2007] rgxsxrs - P8522 [IOI2021] 地牢游戏 - CF1515I Phoenix and Diamonds