数据结构清单

清单

初级数据结构

栈

单调队列

• [USACO13NOV]挤奶牛
• 切蛋糕
• 奶牛排队
• [SCOI2010]股票交易(单调队列优化dp)
• [SDOI2008]Sue的小球

总结

一眼看出是O(N)的题？~~仿佛遇到贪心~~
单调队列优化dp

优先队列

• [HNOI2003]操作系统(主要是策清楚模拟什么)
• [HNOI2015]菜肴制作

树状数组(超级思维的)

• [TJOI2017]异或和

线段树(都超级经典)

• [SDOI2011]染色

主席树(戳我有知识讲解)

• [模板]可持久化线段树1(主席树)(静态)
• Dynamic Rankings(动态)
• [SCOI2016]美味(静态)
• [NOI2010]超级钢琴
• [HNOI2015]开店

左偏树(戳我有知识讲解)

• 崎岖的山路
• Monkey King
• [JLOI2015]城池攻占(我也没有用$fa[x]$)(位于榜二)
• [APIO2012]派遣(此题不用记$fa[x]$)
• 逃跑的BarnRunning(此题我记了$fa[x]$)
• 2.23考试T2(注意维护中位数)
• [JLOI2015]装备购买
• [SCOI2008]斜堆

总结
貌似并不支持很多操作？

维护集合之间的信息(~~我们不是有启发式合并吗~~)
静态维护区间中位数

可持久化并查集&数组

• [模板]可持久化并查集(注意没有路径压缩而是按秩合并)
• [模板]可持久化数组

Splay(戳我有知识讲解)

• [模板]普通平衡树
• [模板]文艺平衡树
• [HNOI2012]永无乡(另涉及根的细节和启发式合并，值得回味)
• [ZJOI2006]书架
• 书架Bookshelf
• [HNOI2004]宠物收养场
• [HNOI2002]营业额统计
• 送花
• [NOI2004]郁闷的出纳员
• [CQOI2014]排序机械臂(不用存v值的Splay???)
• [HNOI2009]梦幻布丁(熟悉set用法)
• [NOI2005]维护数列
• [NOIP2017]列队

总结
$Splay$所支持的操作有很多，暂时总结一些奇技淫巧

*动态维护整体第K_th大
支持查找前驱后继
套上并查集与启发式合并动态维护连通性


*区间翻转，查询，插入，删除，修改，平移
利用线段树建树思想来快速做到Insert

还有骚操作就是维护多棵Splay，每棵Splay维护一个区间(但是没有将所有的值域插入!)，加点删点考虑拆点的思想

值得注意的是

弄清楚是位置Splay还是权值Splay，不然到时候节点存的值都策不清
有时为了防止是道裸的数据结构题，经常会卡空间，所以需要掌握各种省空间技巧，例如动态开点，维护选点集合，插入点可以是之前删除点(参见维护数列)等等技巧，需要更加熟练

Link-Cut Tree(戳我有知识讲解)(戳我有题目推荐)

• [模板]Link Cut Tree
• [国家集训队]Tree II(人生第二道黑题)
• [HNOI2010]弹飞绵羊
• [SDOI2008]Cave 洞穴勘测(只需维护连通性)
• [ZJOI2012]网络
• [SDOI2014]旅行
• [WC2006]水管局长
• [NOI2014]魔法森林(一道不错的用LCT维护最小生成树的题)
• 温暖会指引我们前行
• [国家集训队]旅游

树链剖分

• [HNOI2016]网络

可持久化Trie树(利用可持久化实现区间询问)

• 最大异或和
• [TJOI2018]异或(Get到一个东西)
• [BZOJ4103] (权限题)

树套树

• [模板]二逼平衡树
• [ZJOI2013]K大数查询
• [HEOI2016/TJOI2016]序列
• [CTSC2008]网络管理Network

总结

所以貌似可以用树套树来优化dp

高级数据结构

线段树分治

• 二分图
• [FJOI2015]火星商店问题

线段树合并

• [Poi2011]Tree Rotations

虚树(戳我有知识讲解)

• [SDOI2011]消耗战
• [HNOI2014]世界树(真的♂)
• [HEOI2014]大工程

K-D树

• CF1010E Store(戳我有题解)

1.替罪羊树
2.带花树
3.回文树