Menci

眉眼如初,岁月如故

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


  1. 「BZOJ 1396」识别子串 - SAM + 线段树

    对于一个字符串 S S ,和 S S 中的第 i i 个字符 x x ,定义子串 T=S(ij) T = S(i \ldots j) 为一个关于 x x 的识别子串,当且仅当:

    1. ixj i \leq x \leq j
    2. T T S S 中只出现一次。

    S S 关于每一位字符的最短识别子串长度。

    于  BZOJ, SAM, 李超树, 线段树 继续阅读

  2. 「BZOJ 4499」线性函数 - 线段树

    小 C 最近在学习线性函数,线性函数可以表示为 f(x)=kx+b f(x) = kx + b 。现在小 C 面前有 n n 个线性函数 fi(x)=kix+bi f_i(x) = k_ix+b_i ,他对这 n n 个线性函数执行 m m 次操作,每次可以:

    1. M i K B 代表把第 i i 个线性函数改为 fi(x)=kx+b f_i(x) = kx + b
    2. Q l r x 返回

    于  BZOJ, 线段树 继续阅读

  3. 「BZOJ 3674」可持久化并查集加强版 - 可持久化线段树

    n n 个集合,m m 个操作:

    • 1 a b 合并 a a b b 所在集合;
    • 2 k 回到第 k k 次操作之后的状态(查询算作操作);
    • 3 a b 询问 a a b b 是否属于同一集合,是则输出 1 1 否则输出 0 0

    于  BZOJ, 可持久化并查集, 可持久化数据结构, 可持久化线段树, 数据结构, 线段树 继续阅读

  4. 「BZOJ 3673」可持久化并查集 - 可持久化线段树

    n n 个集合,m m 个操作:

    • 1 a b 合并 a a b b 所在集合;
    • 2 k 回到第 k k 次操作之后的状态(查询算作操作);
    • 3 a b 询问 a a b b 是否属于同一集合,是则输出 1 1 否则输出 0 0

    于  BZOJ, 可持久化并查集, 可持久化数据结构, 可持久化线段树, 数据结构, 线段树 继续阅读

  5. 「SHOI2008」堵塞的交通 - 线段树

    整个国家的交通系统可以被看成是一个 2 2 C C 列的矩形网格,网格上的每个点代表一个城市,相邻的城市之间有一条道路,所以总共有 2C 2C 个城市和 3C2 3C - 2 条道路。

    交通信息可以分为以下几种格式:

    1. Close r1 c1 r2 c2,相邻的两座城市 (r1,c1) (r_1, c_1) (r2,c2) (r_2, c_2) 之间的道路被堵塞了;
    2. Open r1 c1 r2 c2,相邻的两座城市 (r1,c1) (r_1, c_1) (r2,c2) (r_2, c_2) 之间的道路被疏通了;
    3. Ask r1 c1 r2 c2,询问城市 (r1,c1) (r_1, c_1) (r2,c2) (r_2, c_2) 是否连通。

    于  BZOJ, SHOI, 线段树 继续阅读

  6. 「NOIP2012」借教室 - 二分 / 线段树

    我们需要处理接下来 n n 天的借教室信息,其中第 i i 天学校有 ri r_i 个教室可供租借。共有 m m 份订单,每份订单用三个正整数描述,分别为 dj,sj,tj d_j, s_j, t_j ,表示某租借者需要从第 sj s_j 天到第 tj t_j 天租借教室(包括第 sj s_j 天和第 tj t_j 天),每天需要租借 dj d_j 个教室。

    现在我们需要知道,是否会有订单无法完全满足。如果有,需要通知哪一个申请人修改订单。

    于  COGS, CodeVS, NOIP, 二分, 差分, 线段树 继续阅读

  7. 「NOI2016」区间 - 线段树

    在数轴上有 n n 个闭区间 [l1,r1],[l2,r2],,[ln,rn] [l_1, r_1], [l_2, r_2] , \ldots, [l_n, r_n] 。现在要从中选出 m m 个区间,使得这 m m 个区间共同包含至少一个位置。换句话说,就是使得存在一个 x x ,使得对于每一个被选中的区间 [li,ri] [l_i, r_i] ,都有 lixri l_i \leq x \leq r_i

    对于一个合法的选取方案,它的花费为被选中的最长区间长度减去被选中的最短区间长度。区间 [li,ri] [l_i, r_i] 的长度定义为 ,即等于它的右端点的值减去左端点的值。

    求所有合法方案中最小的花费。

    于  BZOJ, NOI, 线段树 继续阅读

  8. 「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, 数据结构, 线段树 继续阅读

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

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

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

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

  10. 「SDOI2016」游戏 - 树链剖分

    Alice 和 Bob 在玩一个游戏。
    游戏在一棵有 n n 个点的树上进行。最初,每个点上都只有一个数字,那个数字是 123456789123456789 123456789123456789
    有时,Alice 会选择一条从 s s t t 的路径,在这条路径上的每一个点上都添加一个数字。对于路径上的一个点 r r ,若 r r s s 的距离是 dis dis ,那么 Alice 在点 r r 上添加的数字是 a×dis+b a \times dis + b
    有时,Bob 会选择一条从 s s t t 的路径。他需要先从这条路径上选择一个点,再从那个点上选择一个数字。
    Bob 选择的数字越小越好,但大量的数字让 Bob 眼花缭乱。Bob 需要你帮他找出他能够选择的最小的数字。

    于  BZOJ, COGS, SDOI, 数学, 数据结构, 最近公共祖先, 李超树, 树链剖分, 线段树 继续阅读