#P18182. Normal Friends

Normal Friends

Normal Friends

小 Q 很喜欢线段树。普通线段树在处理区间 [l,r][l,r] 时,取 mid=⌊(l+r)/2⌋mid=\lfloor(l+r)/2\rfloor,把区间分成 [l,mid][l,mid] 和 [mid+1,r][mid+1,r]。现在她研究一种广义线段树:只要求 l≤mid<rl\le mid<r,不要求从中点切分。因此,这棵树可能有 O(n)O(n) 的深度。

整棵树表示区间 [1,n][1,n]。每个叶子表示一个元素,每个非叶子恰有两个孩子;一个节点表示的区间,就是它的子树中所有叶子从左到右占据的位置。

小 Q 想用这种树实现区间反转。对待反转区间,她执行以下操作:

  1. 将该区间划分为若干个由当前树中节点表示的极大子区间。极大的意思是,选中的节点区间包含在待反转区间中,而其父节点区间不完全包含在其中。按从左到右的顺序,设对应节点为 a1,a2,…,aka_1,a_2,\ldots,a_k。
  2. 从树上取下这 kk 棵完整子树,将它们按反序接回原来的 kk 个位置:原来 a1a_1 的位置接上原来 aka_k 的子树,原来 a2a_2 的位置接上原来 ak−1a_{k-1} 的子树,依此类推。
  3. 对接回去的这 kk 棵子树,交换其中每个非叶节点的左右孩子,即分别将每棵子树整体镜像。

操作后,树依然是一棵广义线段树,叶子从左到右的顺序恰好完成了区间反转。不同子树的叶子数可能不同,因此接回后,祖先所表示的区间及切分点也会相应变化;后续操作必须使用当前树的结构。

给定初始广义线段树和 mm 次操作。每次给定 xx,按上述规则反转前缀 [1,x][1,x]。请在每次操作时,输出这次划分得到的子树数量 kk。

输入格式

第一行包含两个整数 n,mn,m,表示叶子数和操作次数。

第二行包含 n−1n-1 个整数,按初始树的 DFS 前序给出所有非叶节点的切分点 midmid。具体而言,从根区间 [1,n][1,n] 开始:对于非叶区间 [l,r][l,r],先读取它的 midmid,然后依次递归访问 [l,mid][l,mid] 和 [mid+1,r][mid+1,r];叶区间不读取切分点。保证每次读取的切分点都满足 l≤mid<rl\le mid<r。

接下来 mm 行,每行一个整数 xx,表示反转当前树中前 xx 个叶子组成的前缀。

输出格式

输出 mm 行,每行一个正整数,表示相应操作中划分得到的极大子树数量 kk。

数据范围

  • 2≤n,m≤3×1052\le n,m\le 3\times10^5;
  • 每次操作满足 1≤x≤n1\le x\le n;
  • 初始树的所有切分点按上述 DFS 规则合法。

本题只有一组数据。每次输出的答案唯一。

样例

输入:

3 3
2 1
2
3
2

输出:

1
1
2

初始根将 [1,3][1,3] 切成 [1,2][1,2] 和 [3,3][3,3],左孩子再切成两个叶子。第一次反转 [1,2][1,2],该区间恰好是一棵完整子树,所以 k=1k=1。第二次反转整棵树,仍有 k=1k=1。此后根的左孩子只有一个叶子,右孩子有两个叶子;第三次反转前两个位置,需要选中两棵单叶子子树,所以 k=2k=2。