Menci

眉眼如初,岁月如故

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


  1. 「BZOJ 2555」SubString - SAM + LCT

    1. 在当前字符串的后面插入一个字符串;
    2. 询问字符串 s s 在当前字符串中出现了几次?(作为连续子串)

    于  BZOJ, Link-Cut Tree, SAM, 字符串, 数据结构 继续阅读

  2. 「BZOJ 2588」Count on a tree - 主席树

    给定一棵 N N 个节点的树,每个点有一个权值,对于 M M 个询问 (u,v,k) (u, v, k) ,你需要回答 u u v v 这两个节点间第 k k 小的点权。

    于  BZOJ, 主席树, 数据结构, 最近公共祖先 继续阅读

  3. 「CQOI2015」任务查询系统 - 主席树

    最近实验室正在为其管理的超级计算机编制一套任务管理系统,而你被安排完成其中的查询部分。超级计算机中的任务用三元组 (Si,Ei,Pi) (S_i, E_i, P_i) 描述,(Si,Ei,Pi) (S_i, E_i, P_i) 表示任务从第 Si S_i 秒开始,在第 Ei E_i 秒后结束(第 Si S_i 秒和 Ei E_i 秒任务也在运行),其优先级为 Pi P_i 。同一时间可能有多个任务同时执行,它们的优先级可能相同,也可能不同。调度系统会经常向查询系统询问,第 Xi X_i 秒正在运行的任务中,优先级最小的 Ki K_i 个任务(即将任务按照优先级从小到大排序后取前 Ki K_i 个)的优先级之和是多少。特别的,如果 Ki K_i 大于第 Xi X_i 秒正在运行的任务总数,则直接回答第 Xi X_i 秒正在运行的任务优先级之和。上述所有参数均为整数,时间的范围在 1 1 n n 之间(包含 1 1 n n )。

    于  BZOJ, CQOI, 主席树, 数据结构 继续阅读

  4. 「BZOJ 3376」Cube Stacking - 带权并查集

    约翰和贝茜在玩一个方块游戏。编号为 1 1 n n n n 个方块正放在地上.每个构成一个立方柱。

    游戏开始后,约翰会给贝茜发出 m m 个指令。指令有两种:

    1. 移动:将包含 x x 的立方柱移动到包含 y y 的立方柱上;
    2. 统计:统计名含 x x 的立方柱中,在 x x 下方的方块数目。

    写个程序帮贝茜完成游戏。

    于  BZOJ, 并查集, 数据结构 继续阅读

  5. 「WC2013」糖果公园 - 树链剖分 + 莫队

    Candyland 有一座糖果公园,公园里不仅有美丽的风景、好玩的游乐项目,还有许多免费糖果的发放点,这引来了许多贪吃的小朋友来糖果公园玩。

    糖果公园的结构十分奇特,它由 n n 个游览点构成,每个游览点都有一个糖果发放处,我们可以依次将游览点编号为 1 1 n n 。有 n1 n - 1 双向道路连接着这些游览点,并且整个糖果公园都是连通的,即从任何一个游览点出发都可以通过这些道路到达公园里的所有其它游览点。

    糖果公园所发放的糖果种类非常丰富,总共 m m 种,它们的编号依次为 1 1 m m 。每一个糖果发放处都只发放某种特定的糖果,我们用 ci c_i 来表示 i i 号游览点的糖果。

    来到公园里游玩的游客都不喜欢走回头路,他们总是从某个特定的游览点出发前往另一个特定的游览点,并游览途中的景点,这条路线一定是唯一的。他们经过每个游览点,都可以品尝到一颗对应种类的糖果。

    大家对不同类型的糖果的喜爱程度都不尽相同。根据游客们的反馈打分,我们得到了糖果的美味指数,第 i i 种糖果的美味指数为 vi v_i 。另外,如果一位游客反复地品尝同一种类的糖果,他肯定会觉得有一些腻。根据量化统计,我们得到了游客第 i i 次品尝某类糖果的新奇指数 wi w_i ,如果一位游客第 i i 次品尝第 j j 种糖果,那么他的愉悦指数 H H 将会增加对应的美味指数与新奇指数的乘积,即 vjwi v_j w_i 。这位游客游览公园的愉悦指数最终将是这些乘积的和。

    当然,公园中每个糖果发放点所发放的糖果种类不一定是一成不变的。有时,一些糖果点所发放的糖果种类可能会更改(也只会是 m m 种中的一种),这样的目的是能够让游客们总是感受到惊喜。 糖果公园的工作人员小 A 接到了一个任务,那就是根据公园最近的数据统计出每位游客游玩公园的愉悦指数。但数学不好的小 A 一看到密密麻麻的数字就觉得头晕,作为小 A 最好的朋友,你决定帮他一把。

    于  BZOJ, WC, 数据结构, 最近公共祖先, 树链剖分, 莫队 继续阅读

  6. 「SDOI2009」HH 的项链 - 莫队

    给一个长度为 n n 的序列,每次查询一个区间中不同的数的个数。

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

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

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

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

  8. 「NOI2005」维修数列 - Splay

    请写一个程序,要求维护一个数列,支持以下 6 6 种操作。

    操作 输入格式 说明
    插入 INSERT pos cnt a[1] a[2] ...... a[cnt] 在当前数列的第 pos \text{pos} 个数字后插入 cnt \text{cnt} 个数字:a1,a2,acnt a_1, a_2 \ldots, a_{\text{cnt}} ,如果 pos=0 \text{pos} = 0 ,则在首部插入
    删除 DELETE pos cnt 从当前数列的第 pos \text{pos} 个数字开始,删除连续的 cnt \text{cnt} 个数字
    修改 MAKE-SAME pos cnt x 将当前数列的第 pos \text{pos} 个数字开始的连续 cnt \text{cnt} 个数字统一修改为 x x
    翻转 REVERSE pos cnt 取出当前数列的第 pos \text{pos} 个数字开始的连续 cnt \text{cnt} 个数字,翻转后放入原来的位置
    求和 GET-SUM pos cnt x 计算从当前数列的第 pos \text{pos} 个数字开始的连续 cnt \text{cnt} 个数字的和并输出
    最大子段和 MAX-SUM 求出当前数列中和最大的一段子序列,并输出其和

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

  9. 「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, 可持久化并查集, 可持久化数据结构, 可持久化线段树, 数据结构, 线段树 继续阅读

  10. 「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, 可持久化并查集, 可持久化数据结构, 可持久化线段树, 数据结构, 线段树 继续阅读