数据结构 (一)

这个 brief 写得好煞笔啊，看看就行了莫当真。 [数据结构 (二)](https://www.luogu.com.cn/training/13245) 和同学搞的东西，有兴趣就看看吧。 ## 平衡树 [P2234 [HNOI2002]营业额统计](https://www.luogu.com.cn/problem/P2234) 普通平衡树水题 [P3988 [SHOI2013]发牌](https://www.luogu.com.cn/problem/P3988) 权值线段树和普通平衡树都能做 [SP4487 GSS6 - Can you answer these queries VI](https://www.luogu.com.cn/problem/SP4487) 平衡树水题，可以做累了养养生 [P3165 [CQOI2014]排序机械臂](https://www.luogu.com.cn/problem/P3165) 区间平衡树比较经典的题目 [「2018 集训队互测 Day 3」北校门外的未来](https://loj.ac/problem/2474) 贼\*\*神仙的LCT+笛卡尔树，当初调死我了 ## 分块/根号分治 [P3793 由乃救爷爷](https://www.luogu.com.cn/problem/P3793) lxl爷的题。虽然不是Ynoi，但我们依然知道肯定是分块/xyx [P5309 [Ynoi2011]初始化](https://www.luogu.com.cn/problem/P5309) 分块+根号分治 ## 莫队 [P4688 [Ynoi2016]掉进兔子洞](https://www.luogu.com.cn/problem/P4688) 莫队+分批处理询问卡空间 [P3674 小清新人渣的本愿](https://www.luogu.com.cn/problem/P3674) 莫队bitset [P3709 大爷的字符串题](https://www.luogu.com.cn/problem/P3709) 莫队练手题，推荐给刚学莫队的 [P5072 [Ynoi2015]盼君勿忘](https://www.luogu.com.cn/problem/P5072) 比较棒的一道题，ds100p一半的纪念题。 ## 主席树 [P3302 [SDOI2013]森林](https://www.luogu.com.cn/problem/P3302) 启发式合并+主席树 [P2163 [SHOI2007]园丁的烦恼](https://www.luogu.com.cn/problem/P2163) 水板题 [P2163 [SHOI2007]园丁的烦恼](https://www.luogu.com.cn/problem/P2163) LYC版 ## ODT [数列分块入门 8](https://loj.ac/problem/6284) 谁会老老实实打分块啊/xyx [P5350 序列](https://www.luogu.com.cn/problem/P5350) ODTnb ## 树链剖分 [P2633 Count on a tree](https://www.luogu.com.cn/problem/P2633) 树剖+主席树 [P3250 [HNOI2016]网络](https://www.luogu.com.cn/problem/P3250) 暴力三个log的树剖 [P4211 [LNOI2014]LCA](https://www.luogu.com.cn/problem/P4211) 典型的树剖题 [P3313 [SDOI2014]旅行](https://www.luogu.com.cn/problem/P3313) 水题，推荐给树剖新手 ## 树状数组 [SP3267 DQUERY - D-query](https://www.luogu.com.cn/problem/SP3267) 套路排序再BIT [P3997 [SHOI2013]扇形面积并](https://www.luogu.com.cn/problem/P3997) 有BIT做法 [P4309 [TJOI2013]最长上升子序列](https://www.luogu.com.cn/problem/P4309) vector暴力insert+BIT维护 [CF383C Propagating tree](https://www.luogu.com.cn/problem/CF383C) DFS序拍平成序列维护两个树状数组 [\*\*BZOJ7046 分糖果](http://61.186.173.89:2019/2020/06/30/0b9e401fd4fb9.png) 二分checkdpBIT优化 ## 线段树 [P1848 [USACO12OPEN]Bookshelf G](https://www.luogu.com.cn/problem/P1848) 主旋律是DP，但也不失为一道练习线段树的好题 [P3688 [ZJOI2017]树状数组](https://www.luogu.com.cn/problem/P3688) 二维线段树好题 [P1121 环状最大两段子段和](https://www.luogu.com.cn/problem/P1121) 水题，以前蓝的，现在绿了 [P2471 [SCOI2007]降雨量](https://www.luogu.com.cn/problem/P2471) 致命分类讨论 [P2824 [HEOI2016/TJOI2016]排序](https://www.luogu.com.cn/problem/P2824) 很妙的一道题，值得一做！ [P1712 [NOI2016]区间](https://www.luogu.com.cn/problem/P1712) SGT套个贪心，不难 [P5524 [Ynoi2012]NOIP2015洋溢着希望/P6327 区间加区间sin和](https://www.luogu.com.cn/problem/P6327) 知道公式就很水 [P3224 [HNOI2012]永无乡](https://www.luogu.com.cn/problem/P3224) 线段树合并板题 ## LCT [P1110 [ZJOI2007]报表统计](https://www.luogu.com.cn/problem/P1110) 野蛮LCT，比较板 [P3690 【模板】Link Cut Tree （动态树）](https://www.luogu.com.cn/problem/P3690) LCT模板 [P5227 [AHOI2013]连通图](https://www.luogu.com.cn/problem/P5227) LCT最大生成树 [P3203 [HNOI2010]弹飞绵羊](https://www.luogu.com.cn/problem/P3203) LCT好题，需要转化一下 [P2486 [SDOI2011]染色](https://www.luogu.com.cn/problem/P2486) 正解树剖，我打的LCT [P4172 [WC2006]水管局长](https://www.luogu.com.cn/problem/P4172) LCT维护MST比较经典的题目 [P5220 特工的信息流](https://www.luogu.com.cn/problem/P5220) LCT板题 ## Trie [P4592 [TJOI2018]异或](https://www.luogu.com.cn/problem/P4592) 正解TCS，强行01trie+dfs序 [P5335 [THUSC2016]补退选](https://www.luogu.com.cn/problem/P5335) Trie树水题 [P5795 [THUSC2015]异或运算](https://www.luogu.com.cn/problem/P5795) 比较板的可持久Trie ## 扫描线 [P3997 [SHOI2013]扇形面积并](https://www.luogu.com.cn/problem/P3997) 算是比较经典的扫描线吧 ## 其他 [P2161 [SHOI2009]会场预约](https://www.luogu.com.cn/problem/P2161) STL好！ [P4168 [Violet]蒲公英](https://www.luogu.com.cn/problem/P4168) ~~洛谷数据水，离散化暴力能过~~ [P4168 [Violet]蒲公英](https://www.luogu.com.cn/problem/P4168) ~~LYC给出分块打表做法~~ [CF85D Sum of Medians](https://www.luogu.com.cn/problem/CF85D) ~~数据水得二批，vector模拟直接干~~ [P3620 [APIO/CTSC 2007]数据备份](https://www.luogu.com.cn/problem/P3620) 链表+堆 [P3590 [POI2015]TRZ](https://www.luogu.com.cn/problem/P3590) ~~暴力最慢一个点跑了20ms~~