Menci

眉眼如初,岁月如故

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


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

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

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

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

  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. 莫队算法学习笔记

    算法竞赛中有这样一类题目,给定一个序列 [1, n] [1,\ n] ,每次查询 [l, r] [l,\ r] 区间的信息。这类题目没有修改操作,只有查询,并且操作没有加密(允许离线),莫队算法就是针对这类题目的一个离线算法。

    于  学习笔记, 数据结构, 莫队 继续阅读

  7. 「HNOI2016」序列 - 莫队 + RMQ

    给定长度为 n n 的序列: ,记为 a[1:n] a[1:n] 。类似的,a[l:r] a[l:r] 1lrn 1 \leq l \leq r \leq n )是指序列: 。若 1lstrn 1 \leq l \leq s \leq t \leq r \leq n ,则称 a[s:t] a[s:t] a[l:r] a[l:r] 的子序列。

    现在有 q q 个询问,每个询问给定两个数 l l r r 1lrn 1 \leq l \leq r \leq n ,求 a[l:r] a[l:r] 的不同子序列的最小值之和。

    于  BZOJ, HNOI, RMQ, 莫队 继续阅读

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

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

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