Menci

眉眼如初,岁月如故

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


  1. 「SCOI2015」情报传递 - 离线 + Link-Cut Tree

    奈特公司有着庞大的情报网络。情报网络中共有 n n 名情报员。每名情报员有若干名下线,除 1 名大头目外其余 n1 n - 1 名情报员有且仅有 1 名上线。每名情报员只能与自己的上、下线联系,同时,情报网络中任意两名情报员一定能够通过情报网络传递情报。 奈特公司每天会派发以下两种任务中的一个任务:

    1. 搜集情报:指派 T T 号情报员搜集情报;
    2. 传递情报:将一条情报从 X X 号情报员传递给 Y Y 号情报员。

    情报员最初处于潜伏阶段,危险值为 0;一旦某个情报员开始搜集情报,他的危险值就会持续增加,每天增加 1 点危险值(开始搜集情报的当天危险值仍为 0,第 2 天危险值为 1,以此类推)。传递情报并不会使情报员的危险值增加。

    为了保证传递情报的过程相对安全,每条情报都有一个风险控制值 C C 。公司认为,传递这条情报的所有情报员中,危险值大于 C C 的情报员将对该条情报构成威胁。现在,奈特公司希望知道,对于每个传递情报任务,参与传递的情报员有多少个,其中对该条情报构成威胁的情报员有多少个。

    于  BZOJ, Link-Cut Tree, SCOI, 安徽集训, 数据结构, 离线, 高级数据结构 继续阅读

  2. 「省选模拟赛」染色 - 树链剖分

    给定一棵 n n 个节点的树,树的节点标号从 0 0 开始。每个节点可以是白色或黑色,初始时每个节点的颜色为白色。要求支持以下两种操作:

    1. 将节点 x x 涂黑;
    2. 查询节点 x x 到所有黑点距离之和。

    于  安徽集训, 数据结构, 树链剖分, 线段树, 高级数据结构 继续阅读

  3. 「SDOI2008」洞穴勘测 - Link-Cut Tree

    如果监测到洞穴 u u 和洞穴 v v 之间出现了一条通道,终端机上会显示一条指令 Connect u v;如果监测到洞穴 u u 和洞穴 v v 之间的通道被毁,终端机上会显示一条指令 Destroy u v。辉辉希望能随时通过终端机发出指令 Query u v,向监测仪询问此时洞穴 u u 和洞穴 v v 是否连通。已知在第一条指令显示之前,洞穴群中没有任何通道存在。

    于  BZOJ, CodeVS, Link-Cut Tree, SDOI, 动态树, 数据结构, 高级数据结构 继续阅读

  4. 「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, 数据结构, 高级数据结构 继续阅读

  5. 「JSOI2008」最大数 - Splay

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

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

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

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

  6. 「BZOJ 1756」小白逛公园 - 线段树

    路的一边从南到北依次排着 n 个公园,一开始,小白就根据公园的风景给每个公园打了分。小新为了省事,每次遛狗的时候都会事先规定一个范围,小白只可以选择第 a 个和第 b 个公园之间(包括 ab 两个公园)选择连续的一些公园玩。小白当然希望选出的公园的分数总和尽量高咯。同时,由于一些公园的景观会有所改变,所以,小白的打分也可能会有一些变化。那么,就请你来帮小白选择公园吧。

    于  BZOJ, DP, 数据结构, 线段树, 高级数据结构 继续阅读

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

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

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

  8. 「NOI2015」软件包管理器 - 树链剖分

    你决定设计你自己的软件包管理器。不可避免地,你要解决软件包之间的依赖问题。如果软件包 A 依赖软件包 B,那么安装软件包 A 以前,必须先安装软件包 B。同时,如果想要卸载软件包 B,则必须卸载软件包A。现在你已经获得了所有的软件包之间的依赖关系。而且,由于你之前的工作,除 0 号软件包以外,在你的管理器当中的软件包都会依赖一个且仅一个软件包,而 0 号软件包不依赖任何一个软件包。依赖关系不存在环,当然也不会有一个软件包依赖自己。用户希望在安装和卸载某个软件包时,快速地知道这个操作实际上会改变多少个软件包的安装状态。

    于  BZOJ, CodeVS, NOI, 数据结构, 树链剖分, 高级数据结构 继续阅读

  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, 学习笔记, 数据结构, 高级数据结构 继续阅读