Menci

眉眼如初,岁月如故

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


  1. 「APIO2012」Dispatching - 左偏树

    给定一棵 n n 个点的有根树,每个点有两个属性 Ci C_i Li L_i ,现在你要指定一个点 R R ,并在 R R 的子树内选取若干点(可以选取 R R 自己),使得这些点的 Ci C_i 的和不超过 M M ,而一个选取方案的价值为选取人数 ×LR \times L_R ,求选取方案的最大价值。

    于  APIO, BZOJ, 左偏树, 数据结构 继续阅读

  2. 「SCOI2005」王室联邦 - 树分块

    他想把他的国家划分成若干个省,每个省都由他们王室联邦的一个成员来管理。他的国家有 n n 个城市,编号为 1n 1 \ldots n 。一些城市之间有道路相连,任意两个不同的城市之间有且仅有一条直接或间接的道路。

    每个省至少要有 B B 个城市,最多只有 3B 3B 个城市。

    每个省必须有一个省会,这个省会可以位于省内,也可以在该省外。但是该省的任意一个城市到达省会所经过的道路上的城市(除了最后一个城市,即该省省会)都必须属于该省。

    一个城市可以作为多个省的省会。

    于  BZOJ, SCOI, 分块, 数据结构, 树分块 继续阅读

  3. 「AHOI2013」作业 - 莫队

    给一个长度为 n n 的序列,每次查询一个区间 x[l,r] x \in [l, r] 内满足 aixbi a_i \leq x \leq b_i x x 的数量和不重复的 x x 的数量。

    于  AHOI, BZOJ, 数据结构, 莫队 继续阅读

  4. 「BZOJ 3289」Mato 的文件管理 - 莫队

    给一个长度为 n n 的序列,每次求一个区间 [l,r] [l, r] 的逆序对数。

    于  BZOJ, 数据结构, 莫队 继续阅读

  5. 「BZOJ 2120」数颜色 - 带修改莫队

    墨墨购买了一套 N N 支彩色画笔(其中有些颜色可能相同),摆成一排,你需要回答墨墨的提问。
    墨墨会像你发布如下指令:

    1. Q L R 代表询问你从第 L L 支画笔到第 R R 支画笔中共有几种不同颜色的画笔。
    2. R P Col 把第 P P 支画笔替换为颜色 Col \text{Col}

    为了满足墨墨的要求,你知道你需要干什么了吗?

    于  BZOJ, 数据结构, 莫队 继续阅读

  6. RMQ 模板

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

    zyz 大佬的评价

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

  7. Splay 模板 + 详细注释

    普通平衡树的模板。

    插入、查询、删除、前趋、后继、排名、选择。

    zyz 大佬的评价

    于  Splay, 数据结构, 算法模板, 高级数据结构 继续阅读

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

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

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

  9. 「Codeforces 716E」Digit Tree - 点分治

    给一棵树,每一条边上有一个 [1,9] [1, 9] 内的数字,求有多少有序点对 (u,v) (u, v) 满足,将 u u v v 的最短路上所有边上的数字连接成一个数,这个数是 m m 的倍数。其中 gcd(m,10)=1 \gcd(m, 10) = 1

    于  Codeforces, 乘法逆元, 数学, 数据结构, 数论, 点分治 继续阅读

  10. 「SDOI2014」旅行 - 树链剖分

    给一棵树,每个点有其初始颜色和权值,每次修改一个点的颜色或权值,查询路径上颜色与起点相同点权值的和或最大值。

    于  BZOJ, SDOI, 数据结构, 树链剖分 继续阅读