#P18182. Normal Friends
Normal Friends
Normal Friends
小 Q 很喜欢线段树。普通线段树在处理区间 时,取 ,把区间分成 和 。现在她研究一种广义线段树:只要求 ,不要求从中点切分。因此,这棵树可能有 的深度。
整棵树表示区间 。每个叶子表示一个元素,每个非叶子恰有两个孩子;一个节点表示的区间,就是它的子树中所有叶子从左到右占据的位置。
小 Q 想用这种树实现区间反转。对待反转区间,她执行以下操作:
- 将该区间划分为若干个由当前树中节点表示的极大子区间。极大的意思是,选中的节点区间包含在待反转区间中,而其父节点区间不完全包含在其中。按从左到右的顺序,设对应节点为 。
- 从树上取下这 棵完整子树,将它们按反序接回原来的 个位置:原来 的位置接上原来 的子树,原来 的位置接上原来 的子树,依此类推。
- 对接回去的这 棵子树,交换其中每个非叶节点的左右孩子,即分别将每棵子树整体镜像。
操作后,树依然是一棵广义线段树,叶子从左到右的顺序恰好完成了区间反转。不同子树的叶子数可能不同,因此接回后,祖先所表示的区间及切分点也会相应变化;后续操作必须使用当前树的结构。
给定初始广义线段树和 次操作。每次给定 ,按上述规则反转前缀 。请在每次操作时,输出这次划分得到的子树数量 。
输入格式
第一行包含两个整数 ,表示叶子数和操作次数。
第二行包含 个整数,按初始树的 DFS 前序给出所有非叶节点的切分点 。具体而言,从根区间 开始:对于非叶区间 ,先读取它的 ,然后依次递归访问 和 ;叶区间不读取切分点。保证每次读取的切分点都满足 。
接下来 行,每行一个整数 ,表示反转当前树中前 个叶子组成的前缀。
输出格式
输出 行,每行一个正整数,表示相应操作中划分得到的极大子树数量 。
数据范围
- ;
- 每次操作满足 ;
- 初始树的所有切分点按上述 DFS 规则合法。
本题只有一组数据。每次输出的答案唯一。
样例
输入:
3 3
2 1
2
3
2
输出:
1
1
2
初始根将 切成 和 ,左孩子再切成两个叶子。第一次反转 ,该区间恰好是一棵完整子树,所以 。第二次反转整棵树,仍有 。此后根的左孩子只有一个叶子,右孩子有两个叶子;第三次反转前两个位置,需要选中两棵单叶子子树,所以 。