【OpenJudge】【数据结构】全题解

Challenge0 : 直接数组模拟即可。

Challenge1 : 比上一题加强了一点，对每个位置建立链表，修改时向该位置插入新节点并保存时间戳，查询时沿着链表找到第一个时间戳小于k的数字

Challenge2:比上一题更难了，可以撤销前x次操作。我们可以使用可持久化的思想，每次操作都新建节点，用倍增思想维护当前节点的祖先，这样查询就可以做到O(logn)

Challenge3 : 裸线段树

Challenge4 : 同样是线段树，其中询问2 =左儿子相邻乘积 * 右儿子相邻乘积 +左儿子右端点 * 右儿子左端点，询问3 = 左儿子两两乘积 * 右儿子两两乘积 + 左儿子区间和 * 右儿子区间和。(注意考虑值为负的情况)

Challenge5 : 线段树 +懒标记

Challenge6 : 至今未做出来，其中一种可行方法就是用类似动态凸包的方法。另外一种分块求凸包的方法没听懂orz。。

Challenge7 : SBT维护，节点有两个域，一个是当前节点的值，另一个是当前值在数列中出现了几次。

Challenge8 : 维护两个SBT，一个是原数列，另一个是原数列排序后的两两差值，插入一个数，就插入到第一个SBT中，找到前趋和后继，插入差值到第二个SBT中；删除一个数，找到前趋后继，在第二个SBT中删除两个差值，并且插入后继 - 前趋的值，再从第一个SBT中删除即可。

Challenge9 : 裸splay

Challenge10 : 裸SBT

Challenge11 : 主席树

Challenge12 : 主席树或者划分树

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!