山有木兮木有枝
心悦君兮君不知

标签 线段树 下的文章

傻逼题,CF 的数据是假的,不开 std::multiset 都可以过。

发现我们直接缩成一棵广义圆方树然后进行维护。修改点权的时候如果我们暴力修改圆点周围的方点显然可能挂掉,但是如果我们的方点只存圆方树上孩子的信息,那么就只用更新 O(1) 次了,这样的话在求 u \rightarrow v 的路径的时候判断一下 LCA 是不是方点即可。时间复杂度 O(n \log^2 n)

READ MORE

对于一个 1 \cdots n (n \leq 5 \times 10^5) 的排列 p_{1 \cdots n} ,定义 next_i 为第一个 j 满足 i < j, p_i < p_j ,如果不存在这样的 j ,则 next_i = n + 1 。给定一个缺失若干位的 next 数组,求构造任一合法的 p 数组。

READ MORE

傻逼题,写来放松身心。

考虑到 \displaystyle dep_u^k = \sum_{i=0}^{\infty} dep_{fa^i(u)}^k - dep_{fa^{i+1}(u)}^k,假设我们要求 \displaystyle dep_{\operatorname{lca}(u, v)},可以把 u1 的路径上每个点 x 加上 dep_x^k - dep_{fa(x)}^k 的权值,查询时从 v 向根节点跳把沿途的权值加上即可。

离线所有查询到 x 上,扫描 x,树剖维护修改和查询即可。

READ MORE

DP 。用 f_{u, 0} 表示 u 点被染黑的概率,f_{u, 1} 表示 u 点被染白,但是其祖先中有点被染黑的概率,用 f_{u, 2} 表示 u 点被染白,且其祖先没有被染黑的点的概率。所求答案即 \displaystyle{\sum_{i=1}^n f_{i, 0}}

READ MORE

考虑一段数 a_{l..r} 是公差为 k 的等差数列,当且仅当:

  • \max a_{l..r} - \min a_{l..r} = k(r - l)

  • \gcd abs(a_i - a_{i-1}) = k, (i \in (l, r])

  • \max pre_{l..r} < lpre_i 表示 a_i 上一次出现的位置。

线段树维护一下即可。

READ MORE

容易发现答案与旗杆的顺序无关,我们可以把旗杆按照从矮到高的顺序排序,这样的话我们只需要维护两个操作:

  1. 插入一些 0
  2. 给一个前缀整体 +1

考虑每次 +1 操作,除了这个前缀中的最大值,每个数的相对位置不会改变。考虑放到线段树上,对于最大值二分出其区间,对其特殊处理后移即可。

READ MORE

一道非常巧妙的哈希题。

假设我们枚举 j 使得 H_i - H_j = H_j - H_k 。可以发现题意要求的 i < j < kik 必须在 j 的两侧。

可以通过线段树 + 哈希维护

  • 哈希值使得第 k 位的哈希值为 1 当且仅当满足 H_i - H_j = kij 的左侧出现;
  • 哈希值使得第 k 位的哈希值为 0 当且仅当满足 H_j - H_i = kij 的右侧出现。

容易发现,若两哈希值不同,即存在一组 ijk 满足条件,我们直接输出 Yes 即可。

另外据称本地数据很弱,乱搞也能过 233 。

READ MORE

我们考虑线段树的本质意义是什么,他可以维护一个序列的可合并的信息。更新的时候需要 merge ,查询的时候需要 merge ,基本上可以合并的内容都可以用线段树维护。

我们来考虑下此题,首先最后的答案可以二分,假设当前二分的 mid 合法当且仅当存在一条链使得 0 ~ mid - 1 都在链上。

这个信息很明显是可以合并的,我们可以用线段树维护。有两点需要注意:

  1. 所谓 l ~ r 都在链上,链上有其他数字也没有关系。

  2. 二分可以直接在线段树上二分,虽然多只 \log 也能过就是了。

READ MORE

首先,我们需要知道如何利用后缀数组对一个指定的字符串计算字典序 Rank 。我们以 abaab 为例:

    a    a    b
   11   10    9
    a    b
    x    8
    a    b    a    a    b
    x    x    7    6    5
    b
    4
    b    a    a    b
    x    3    2    1

按照顺序进行编号,因为本质相同的字符串不重复计算次数,所以每一行的前 height_i 个不计入个数,所以我们也有了一个很自然的 O(n ^ 2) 做法。

接下来我们考虑正解,可以发现,每次可以看做对上面的字典序 Rank 数组进行了依次递减的区间覆盖,可以使用线段树维护。同时我们可以发现,这个 Rank 是递减的,而前缀和是递增的,所以我们可以二分出相等的那个位置。

READ MORE