CF1290E Solution

前言

这道题你需要的前置知识

• 树状数组
• 吉司机线段树的基本操作

正文

题意翻译：给你一个 至 的排列，每次找出其中不大于 的数字，相对位置不变成为一个新的序列，在这个新的序列上建一棵大根笛卡尔树，求这个笛卡尔树的每个结点为根的子树的 size 之和

暴力思想 每次 建笛卡尔树，然后 的 dfs 即可。总复杂度

不难发现一个事情，在我们建这个笛卡尔树的时候，这个序列是 至 的一个排列。其中每个结点的子树他们的编号必定是一个连续的区间，这是因为笛卡尔树满足二叉排序树的性质。

我们记 为以编号为 的结点的子树里的结点的最大编号，同样我们可以定义 。那么每个子树的 size 即为

我们只要求出来 并动态维护他。

考虑现在已经计算了 至 即可。考虑添加一个结点，他的值是 ，这个接待你的编号是 ，在已经添加的序列里是第 个。

• 的结点，如果在序列里，
• 的结点，
• 的结点，如果在序列里，

这样子的话，我们只要每次查询整体序列和即可。

如何判断是否在序列里，我们可以给每个结点打一个 ，表示这个区间里有多少个有用节点，为 直接返回即可，否则我们可以继续递归。

综上，我们需要完成几个操作：

1. 查询上文所述的 ，这个可以通过映射和树状数组完成。
2. 吉司机线段树支持如下操作

• 区间加
• 区间和查询
• 区间 /
• 单点赋值

需要注意的是，我们可以分别维护 和 ，这样子需要写两棵线段树，一棵维护 ，支持区间 ；一棵维护 ，支持区间 ，尽管有不同，但是仅有细小差别。

具体实现可以见代码