Menci

眉眼如初,岁月如故

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


  1. 「BZOJ 2724」蒲公英 - 分块

    给一个长度为 n n 的序列,每次查询一个区间 [l,r] [l, r] 内的众数(如果有多个众数,取最小的一个),强制在线。

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

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

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

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

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

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

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

  3. 「省队集训 2016」Play with array - 块状链表

    有一个长度为 n n 的数列,支持以下两种操作:

    1. ar a_r 移动到 al a_l 的前面;
    2. 查询 [l, r] [l,\ r] k k 的出现次数。

    于  分块, 块状链表, 数据结构, 省队集训 继续阅读

  4. 「HNOI2016」最小公倍数 - 分块 + 并查集

    给定一张 N N 个顶点 M M 条边的无向图(顶点编号为 ),每条边上带有权值。所有权值都可以分解成 2a3b 2 ^ a 3 ^ b 的形式。现在有 q q 个询问,每次询问给定四个参数 u u v v a a b b ,请你求出是否存在一条顶点 u u v v 之间的路径,使得路径依次经过的边上的权值的最小公倍数为 2a3b 2 ^ a 3 ^ b

    于  BZOJ, COGS, CodeVS, HNOI, 分块, 并查集 继续阅读

  5. 「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, 乱搞, 分块 继续阅读

  6. 「BZOJ 2038」小Z的袜子 - 莫队

    给一个数列 x1 x_1 ~ xn x_n ,给出 m m 个询问,每次询问 xi x_i ~ xj x_j 中,任选两个数相同的概率。

    于  BZOJ, 分块, 安徽集训, 莫队 继续阅读