【听课笔记】析合树

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135140754

  • 连续段： r−l=mx−mnr-l=mx-mn ，比如 ｛2，4，3，5｝是，｛3，5｝，｛2，4，3｝不是.

    • 性质1：一个点是连续段，一个排列也是（显然）

    • 性质2：两个连续段的交必为连续段（感性）

  • 本原段：一个连续段，不存在其他连续段和它相交确不包含

一个点表示一个本原段

  • 合点：儿子按顺序递增或递减，比如
    在这里插入图片描述

    • 性质：任选两个点组成的区间也是连续段

  • 析点：不是合点的点。

一个连续段在析合树上的存在形式：

  • 单独一个点：析点或合点

  • 合点的一段儿子区间（方案为 (sze2)2\dfrac{\binom {sze}2}2 ）

因此就可以求一个数列连续段个数。

求一个区间的最小包含连续段

找出原树上两个点，找LCA

  • 若LCA为析点，则这个点就是答案

  • 如果为合点，我们找到对应的两个儿子，它们之间形成的区间就是答案

包含一段区间的连续段个数

显然可以预处理每个点被包含的连续段个数，也就是祖先个数+祖先中合点包括此点的区间数

对于当前查询区间，先前往LCA，如果是析点直接返回这个点的答案，如果是合点还要加上包含 两个儿子区间的答案

查询区间连续段个数

类似zkw，把信息存到链上，然后维护一下即可

构造待补