Menci

眉眼如初,岁月如故

在那无法确定的未来
只愿真心如现在一般清澈


  1. 「NOI2005」维修数列 - Splay

    请写一个程序,要求维护一个数列,支持以下 6 6 种操作。

    操作 输入格式 说明
    插入 INSERT pos cnt a[1] a[2] ...... a[cnt] 在当前数列的第 pos \text{pos} 个数字后插入 cnt \text{cnt} 个数字:a1,a2,acnt a_1, a_2 \ldots, a_{\text{cnt}} ,如果 pos=0 \text{pos} = 0 ,则在首部插入
    删除 DELETE pos cnt 从当前数列的第 pos \text{pos} 个数字开始,删除连续的 cnt \text{cnt} 个数字
    修改 MAKE-SAME pos cnt x 将当前数列的第 pos \text{pos} 个数字开始的连续 cnt \text{cnt} 个数字统一修改为 x x
    翻转 REVERSE pos cnt 取出当前数列的第 pos \text{pos} 个数字开始的连续 cnt \text{cnt} 个数字,翻转后放入原来的位置
    求和 GET-SUM pos cnt x 计算从当前数列的第 pos \text{pos} 个数字开始的连续 cnt \text{cnt} 个数字的和并输出
    最大子段和 MAX-SUM 求出当前数列中和最大的一段子序列,并输出其和

    于  BZOJ, Splay, 数据结构 继续阅读

  2. 「HAOI2008」排名系统 - map + Splay

    排名系统通常要应付三种请求:上传一条新的得分记录、查询某个玩家的当前排名以及返回某个区段内的排名记录。当某个玩家上传自己最新的得分记录时,他原有的得分记录会被删除。为了减轻服务器负担,在返回某个区段内的排名记录时,最多返回 10 10 条记录。对于得分相同的,上传时间早的排名高。

    于  BZOJ, HAOI, Splay, map, 数据结构 继续阅读

  3. 「JSOI2008」火星人 - Splay + Hash

    给定一个字符串,每次修改一个字符、插入一个字符、查询某两个后缀的最长公共前缀。

    于  BZOJ, Hash, JSOI, Splay, 字符串 继续阅读

  4. 「BZOJ 3196」二逼平衡树 - 树套树

    您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:

    1. 查询 k k 在区间内的排名;
    2. 查询区间内排名为 k k 的值;
    3. 修改某一位值上的数值;
    4. 查询 k k 在区间内的前驱(前驱定义为小于 x x ,且最大的数);
    5. 查询 k k 在区间内的后继(后继定义为大于 x x ,且最小的数)。

    于  BZOJ, Splay, 平衡树, 数据结构, 线段树 继续阅读

  5. 「TJOI2013」最长上升子序列 - 离线 + 树状数组

    给定一个序列,初始为空。现在我们将 1 1 N N 的数字插入到序列中,每次将一个数字插入到一个特定的位置。每插入一个数字,我们都想知道此时最长上升子序列长度是多少?

    于  BZOJ, Splay, TJOI, 树状数组, 离线 继续阅读

  6. 「NOI2003」文本编辑器 - Splay

    操作名称 输入文件中的格式 功能
    Move k 将光标移动到第 k k 个字符之后,如果 k=0 k=0 ,将光标移到文本第一个字符之前
    Insert n S 在光标后插入长度为 n n 的字符串 s s ,光标位置不变,
    Delete n 删除光标后的 n n 个字符,光标位置不变,
    Get n 输出光标后的 n n 个字符,光标位置不变,
    Prev 光标前移一个字符
    Next 光标后移一个字符

    于  BZOJ, NOI, Splay, 数据结构, 高级数据结构 继续阅读

  7. 「JSOI2008」最大数 - Splay

    现在请求你维护一个数列,要求提供以下两种操作:

    1. 查询操作。
      语法:Q L
      功能:查询当前数列中末尾 L 个数中的最大的数,并输出这个数的值。
      限制:L 不超过当前数列的长度。
    2. 插入操作。 语法:A n
      功能:将 n 加上 t,其中 t 是最近一次查询操作的答案(如果还未执行过查询操作,则 t = 0),并将所得结果对一个固定的常数 D 取模,将所得答案插入到数列的末尾。
      限制:n 是非负整数并且在长整范围内。

    注意:初始时数列是空的,没有一个数。

    于  BZOJ, JSOI, Splay, 数据结构, 高级数据结构 继续阅读

  8. 「NOI2004」郁闷的出纳员 - Splay

    工资的频繁调整很让员工反感,尤其是集体扣除工资的时候,一旦某位员工发现自己的工资已经低于了合同规定的工资下界,他就会立刻气愤地离开公司,并且再也不会回来了。每位员工的工资下界都是统一规定的。每当一个人离开公司,我就要从电脑中把他的工资档案删去,同样,每当公司招聘了一位新员工,我就得为他新建一个工资档案。老板经常到我这边来询问工资情况,现在工资第 k 多的员工拿多少工资。

    于  BZOJ, CodeVS, NOI, Splay, 数据结构, 高级数据结构 继续阅读

  9. Link-Cut Tree 学习笔记

    Link-Cut Tree 是一种用来维护动态森林连通性的数据结构,适用于动态树问题。它采用类似树链剖分的轻重边路径剖分,把树边分为实边和虚边,并用 Splay 来维护每一条实路径。Link-Cut Tree 的基本操作复杂度为均摊 O(logn)O({\log}n),但常数因子较大,一般效率会低于树链剖分。

    于  Link-Cut Tree, Splay, 动态树, 数据结构, 算法模板, 高级数据结构 继续阅读

  10. Splay 学习笔记(三)

    在《Splay 学习笔记(一)》中,我们学会了利用 Splay 来维护二叉排序树,现在让我们来把我们的 Splay 变得更加优美。

    模板请见《Splay 模板 + 详细注释》

    于  Splay, 学习笔记, 数据结构, 高级数据结构 继续阅读