Menci

眉眼如初,岁月如故

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


  1. 「SDOI2008」校门外的区间 - 线段树

    受校门外的树这道经典问题的启发,A 君根据基本的离散数学的知识,抽象出 5 5 种运算维护集合 S S S S 初始为空)并最终输出 S S 。现在,请你完成这道校门外的树之难度增强版 —— 校门外的区间。

    5 5 种运算如下:

    1. A=AB A = A \cup B
    2. A=AB A = A \cap B
    3. A={xxA and xB} A = \{ x \mid x \in A \ \mathrm{and} \ x \notin B \}
    4. A={xxA and xB} A = \{ x \mid x \notin A \ \mathrm{and} \ x \in B \}
    5. A={xxA and xB}{xxA and xB} A = \{ x \mid x \in A \ \mathrm{and} \ x \notin B \} \cup \{ x \mid x \notin A \ \mathrm{and} \ x \in B \}

    于  BZOJ, SDOI, 数据结构, 线段树 继续阅读

  2. 「NOI2014」魔法森林 - LCT

    魔法森林是一个 N N 个节点 M M 条边的无向图,节点标号为 1N 1 \ldots N ,边标号为 1M 1 \ldots M 。初始时小 E 同学在号节点 1 1 ,隐士在节点 N N

    无向图中的每一条边 Ei E_i 包含两个权值 Ai A_i Bi B_i 。若身上携带的 A 型守护精灵个数不少于 Ai A_i ,且 B 型守护精灵个数不少于 Bi B_i ,这条边上的妖怪就发起攻击。

    小 E 想要知道,要能够成功拜访到隐士,最少需要携带守护精灵的总个数。

    于  BZOJ, LCT, NOI, 数据结构 继续阅读

  3. 「NOI2015」荷马史诗 - 哈夫曼树

    n n 种不同的单词,从 1 1 n n 进行编号。其中第 i i 种单词出现的总次数为 Wi W_i 。要用 k k 进制串 Si S_i 来替换第 i i 种单词,满足对于任意的 1i,jn, ij 1 \leq i,j \leq n,\ i \neq j ,都有:Si S_i 不是 Sj S_j 的前缀。

    1. 替换以后得到的新的长度最小为多少;
    2. 在确保总长度最小的情况下,最长的 Si S_i 的最短长度是多少?

    于  BZOJ, NOI, 哈夫曼树, , 数据结构 继续阅读

  4. 「BZOJ 2716」天使玩偶 - CDQ

    维护一个平面,支持以下两种操作:

    1. 加入点 (x, y) (x,\ y)
    2. 查询麦哈顿距离与点 (x, y) (x,\ y) 最小的点。

    于  BZOJ, CDQ, 分治, 数据结构, 树状数组 继续阅读

  5. 「SHOI2007」园丁的烦恼 - CDQ

    每一棵树可以用一个整数坐标来表示,每次询问你某一个矩阵内有多少树。

    于  BZOJ, CDQ, SHOI, 分治, 数据结构, 树状数组 继续阅读

  6. 「CQOI2011」动态逆序对 - CDQ

    对于序列 A A ,它的逆序对数定义为满足 i<j i < j ,且 Ai>Aj A_i > A_j 的数对 (i, j) (i,\ j) 的个数。给 1 1 n n 的一个排列,按照某种顺序依次删除 m m 个元素,你的任务是在每次删除一个元素之前统计整个序列的逆序对数。

    于  BZOJ, CDQ, CQOI, 分治, 数据结构, 树状数组 继续阅读

  7. 「BZOJ 1176」Mokia - CDQ

    维护一个 N×N N \times N N2000000 N \leq 2000000 )的矩阵,初始值均为 S S 。每次操作可以增加某格子的权值,或询问某子矩阵的总权值。

    修改操作数 160000 \leq 160000 ,询问数 10000 \leq 10000

    于  BZOJ, CDQ, 分治, 数据结构, 树状数组 继续阅读

  8. 「BZOJ 3262」陌上花开 - CDQ

    定义一个序列,序列中每个元素都是一个三元组 Ai=(a, b, c) A_i = (a,\ b,\ c)
    aiaj, bibj, cicj a_i \leq a_j,\ b_i \leq b_j,\ c_i \leq c_j ,则称 Aj A_j Ai A_i 优。
    定义 Ai A_i 的等级为有多少 Aj A_j 满足 Ai A_i Aj A_j 更优。

    求每个等级的元素数量。

    于  BZOJ, CDQ, 分治, 数据结构, 树状数组 继续阅读

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

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

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

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

  10. 点分治学习笔记

    点分治是用来解决树上路径问题的一种方法。

    于  学习笔记, 数据结构, 点分治, 算法模板 继续阅读