Menci

眉眼如初,岁月如故

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


  1. 「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, 线段树 继续阅读

  2. 「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, 二分, 差分, 线段树 继续阅读

  3. 「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, 线段树 继续阅读

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

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

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

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

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

  6. 「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, 数学, 数据结构, 最近公共祖先, 树链剖分, 线段树 继续阅读

  7. 「HAOI2015」树上操作 - 树链剖分 + DFS序

    有一棵点数为 N N 的树,以点 1 1 为根,且树点有边权。然后有 M M 个操作,分为三种:

    1. 把某个节点 x x 的点权增加 a a
    2. 把某个节点 x x 为根的子树中所有点的点权都增加 a a
    3. 询问某个节点 x x 到根的路径中所有点的点权和。

    于  BZOJ, DFS 序, HAOI, 树链剖分, 线段树 继续阅读

  8. 「省选模拟赛」染色 - 树链剖分

    给定一棵 n n 个节点的树,树的节点标号从 0 0 开始。每个节点可以是白色或黑色,初始时每个节点的颜色为白色。要求支持以下两种操作:

    1. 将节点 x x 涂黑;
    2. 查询节点 x x 到所有黑点距离之和。

    于  安徽集训, 数据结构, 树链剖分, 线段树, 高级数据结构 继续阅读

  9. 「BZOJ 1756」小白逛公园 - 线段树

    路的一边从南到北依次排着 n 个公园,一开始,小白就根据公园的风景给每个公园打了分。小新为了省事,每次遛狗的时候都会事先规定一个范围,小白只可以选择第 a 个和第 b 个公园之间(包括 ab 两个公园)选择连续的一些公园玩。小白当然希望选出的公园的分数总和尽量高咯。同时,由于一些公园的景观会有所改变,所以,小白的打分也可能会有一些变化。那么,就请你来帮小白选择公园吧。

    于  BZOJ, DP, 数据结构, 线段树, 高级数据结构 继续阅读