Menci

眉眼如初,岁月如故

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


  1. RMQ 模板

    RMQ 稀疏表(Sparse Table)的模板。

    zyz 大佬的评价

    于  RMQ, 数据结构, 算法模板 继续阅读

  2. 「HNOI2016」序列 - 莫队 + RMQ

    给定长度为 n n 的序列: ,记为 a[1:n] a[1:n] 。类似的,a[l:r] a[l:r] 1lrn 1 \leq l \leq r \leq n )是指序列: 。若 1lstrn 1 \leq l \leq s \leq t \leq r \leq n ,则称 a[s:t] a[s:t] a[l:r] a[l:r] 的子序列。

    现在有 q q 个询问,每个询问给定两个数 l l r r 1lrn 1 \leq l \leq r \leq n ,求 a[l:r] a[l:r] 的不同子序列的最小值之和。

    于  BZOJ, HNOI, RMQ, 莫队 继续阅读

  3. 「JSOI2016」灯塔 - 分块 + RMQ

    JSOI 的国境线上有 N N 一座连续的山峰,其中第 i i 座的高度是 hi h_i 。为了简单起见,我们认为这 N N 座山峰排成了连续一条直线。

    如果在第 i i 座山峰上建立一座高度为 p (p0) p \ (p \geq 0) 的灯塔,JYY 发现,这座灯塔能够照亮第 j j 座山峰,当且仅当满足如下不等式:

    hjhi+pij h_j \leq h_i + p - \sqrt{\mid i - j \mid}

    JSOI 国王希望对于每一座山峰,JYY 都能提供建造一座能够照亮全部其他山峰的灯塔所需要的最小高度。你能帮助 JYY 么?

    于  JSOI, RMQ, 乱搞, 分块 继续阅读

  4. 「SDOI2016」生成魔咒 - 后缀数组

    魔咒串由许多魔咒字符组成,魔咒字符可以用数字表示。例如可以将魔咒字符 1 1 2 2 拼凑起来形成一个魔咒串 [1,2] [1, 2]
    一个魔咒串 S S 的非空字串被称为魔咒串 S S 的生成魔咒。
    例如 S=[1,2,1] S = [1, 2, 1] 时,它的生成魔咒有 [1] [1] [2] [2] [1,2] [1, 2] [2,1] [2, 1] [1,2,1] [1, 2, 1] 五种。S=[1,1,1] S = [1, 1, 1] 时,它的生成魔咒有 [1] [1] [1,1] [1, 1] [1,1,1] [1, 1, 1] 三种。
    最初 S S 为空串。共进行 n n 次操作,每次操作是在 S S 的结尾加入一个魔咒字符。每次操作后都需要求出,当前的魔咒串 S S 共有多少种生成魔咒。

    于  BZOJ, COGS, RMQ, SDOI, 后缀数组, 字符串 继续阅读