CF1290E Solution
前言
这道题你需要的前置知识
- 树状数组
- 吉司机线段树的基本操作
正文
题意翻译:给你一个 至
的排列,每次找出其中不大于
的数字,相对位置不变成为一个新的序列,在这个新的序列上建一棵大根笛卡尔树,求这个笛卡尔树的每个结点为根的子树的
size
之和
暴力思想 每次 建笛卡尔树,然后
的 dfs 即可。总复杂度
不难发现一个事情,在我们建这个笛卡尔树的时候,这个序列是 至
的一个排列。其中每个结点的子树他们的编号必定是一个连续的区间,这是因为笛卡尔树满足二叉排序树的性质。
我们记 为以编号为
的结点的子树里的结点的最大编号,同样我们可以定义
。那么每个子树的
size
即为
我们只要求出来 并动态维护他。
考虑现在已经计算了 至
即可。考虑添加一个结点,他的值是
,这个接待你的编号是
,在已经添加的序列里是第
个。
的结点,如果在序列里,
的结点,
的结点,如果在序列里,
这样子的话,我们只要每次查询整体序列和即可。
如何判断是否在序列里,我们可以给每个结点打一个 ,表示这个区间里有多少个有用节点,为
直接返回即可,否则我们可以继续递归。
综上,我们需要完成几个操作:
- 查询上文所述的
,这个可以通过映射和树状数组完成。
- 吉司机线段树支持如下操作
- 区间加
- 区间和查询
- 区间
/
- 单点赋值
需要注意的是,我们可以分别维护 和
,这样子需要写两棵线段树,一棵维护
,支持区间
;一棵维护
,支持区间
,尽管有不同,但是仅有细小差别。
具体实现可以见代码