数据结构 (一)

题单介绍

这个 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~~

题目列表

  • 环状最大两段子段和
  • DQUERY - D-query
  • 区间加区间 sin 和
  • [SCOI2007] 降雨量
  • [HNOI2002] 营业额统计
  • [SHOI2013] 发牌
  • GSS6 - Can you answer these queries VI
  • [CQOI2014] 排序机械臂
  • [SDOI2013] 森林
  • [SHOI2007] 园丁的烦恼
  • 序列
  • Count on a tree
  • [HNOI2016] 网络
  • [LNOI2014] LCA
  • [SHOI2013] 扇形面积并
  • [USACO12OPEN] Bookshelf G
  • [ZJOI2017] 树状数组
  • [HEOI2016/TJOI2016] 排序
  • [NOI2016] 区间
  • [ZJOI2007] 报表统计
  • 【模板】动态树(LCT)
  • [AHOI2013] 连通图
  • [HNOI2010] 弹飞绵羊
  • [SDOI2011] 染色
  • [WC2006] 水管局长
  • 特工的信息流
  • 小清新人渣的本愿
  • 大爷的字符串题
  • [TJOI2018] 异或
  • [SHOI2009] 会场预约
  • TTM - To the moon
  • [THUSC2016] 补退选
  • [TJOI2013] 最长上升子序列
  • [HNOI2012] 永无乡
  • [SDOI2014] 旅行
  • [POI2015] TRZ
  • [THUSC2015] 异或运算
  • [Ynoi2011] 初始化
  • [APIO/CTSC2007] 数据备份
  • [Ynoi2016] 掉进兔子洞
  • Sum of Medians
  • Propagating tree
  • 由乃救爷爷
  • [Ynoi2015] 盼君勿忘