【系列】数据结构一百题

「洛谷题单界面」，如果有帮助可以 archive 一下。

「洛谷博客界面」

在 mina.moe 上可能更新比较延后，因为我要同时维护多个地方，懒得很……

这里是由 @BoringHacker 以及 @Lautisticyc 维护的数据结构 100 题，简称 DS100P。

难度主要在提高组及以上。颜色一般在紫，除非被爆破成蓝题。除非实在值得一做或被降级，否则该题单不会出现蓝题以下的题。

主要涉及的知识点有 LCT，SGT，BIT，TCS，BT，ODT，TRIE，CT，分块等等数据结构。

DS100P 有其对应的题解！在这里可以找到。并且附赠我和 Lautisticyc 的数据结构学习笔记。

然后就是因为有些题洛谷没有，我就放个其他 OJ 的链接。不过大部分都是洛谷有的历年省选到 NOI 题目。也就是说完整的题目目录在这里而不是题单本体。

目前我们俩做了 46 题，慢慢更嘛~

注意，这里的分类是我和 LYC 用的方法

平衡树

P2234 [HNOI2002] 营业额统计 普通平衡树水题

P3988 [SHOI2013] 发牌 权值线段树和普通平衡树都能做

SP4487 GSS6 – Can you answer these queries VI 平衡树水题，可以做累了养养生

P3165 [CQOI2014] 排序机械臂 区间平衡树比较经典的题目

「2018 集训队互测 Day 3」北校门外的未来 贼** 神仙的 LCT+笛卡尔树，当初调死我了

分块

P3793 由乃救爷爷 lxl 爷的题。虽然不是 Ynoi，但我们依然知道肯定是分块/xyx

莫队

P4688 [Ynoi2016] 掉进兔子洞 莫队+分批处理询问卡空间

P3674 小清新人渣的本愿 莫队 bitset

P3709 大爷的字符串题 莫队练手题，推荐给刚学莫队的

主席树

P3302 [SDOI2013] 森林 启发式合并+主席树

P2163 [SHOI2007] 园丁的烦恼 水板题

P2163 [SHOI2007] 园丁的烦恼 LYC 版

ODT

数列分块入门 8 谁会老老实实打分块啊/xyx

P5350 序列 ODTnb

树链剖分

P2633 Count on a tree 树剖+主席树

P3250 [HNOI2016] 网络 暴力三个 log 的树剖

P4211 [LNOI2014]LCA 典型的树剖题

树状数组

SP3267 DQUERY – D-query 套路排序再 BIT

P3997 [SHOI2013] 扇形面积并 有 BIT 做法

P4309 [TJOI2013] 最长上升子序列 vector 暴力 insert+BIT 维护

分糖果 二分 checkdpBIT 优化

线段树

P1848 [USACO12OPEN]Bookshelf G 主旋律是 DP，但也不失为一道练习线段树的好题

P3688 [ZJOI2017] 树状数组 二维线段树好题

P1121 环状最大两段子段和 水题，以前蓝的，现在绿了

P2471 [SCOI2007] 降雨量 致命分类讨论

P2824 [HEOI2016/TJOI2016] 排序 很妙的一道题，值得一做！

P1712 [NOI2016] 区间 SGT 套个贪心，不难

P5524 [Ynoi2012]NOIP2015 洋溢着希望/P6327 区间加区间 sin 和 知道公式就很水

P3224 [HNOI2012] 永无乡 线段树合并板题

LCT

P1110 [ZJOI2007] 报表统计 野蛮 LCT，比较板

P3690【模板】Link Cut Tree（动态树） LCT 模板

P5227 [AHOI2013] 连通图 LCT 最大生成树

P3203 [HNOI2010] 弹飞绵羊 LCT 好题，需要转化一下

P2486 [SDOI2011] 染色 正解树剖，我打的 LCT

P4172 [WC2006] 水管局长 LCT 维护 MST 比较经典的题目

P5220 特工的信息流 LCT 板题

Trie

P4592 [TJOI2018] 异或 正解 TCS，强行 01trie+dfs 序

P5335 [THUSC2016] 补退选 Trie 树水题

P5795 [THUSC2015] 异或运算 比较板的可持久 Trie

扫描线

P3997 [SHOI2013] 扇形面积并 算是比较经典的扫描线吧

其他

P2161 [SHOI2009] 会场预约 STL 好！

P4168 [Violet] 蒲公英 洛谷数据水，离散化暴力能过

P4168 [Violet] 蒲公英 LYC 给出分块打表做法

CF85D Sum of Medians 数据水得二批，vector 模拟直接干

P3620 [APIO/CTSC 2007] 数据备份 链表+堆

P3590 [POI2015]TRZ 暴力最慢一个点跑了 20ms