提示1 设 p[x]p[x]p[x] 是 xxx 在排列 aaa 中的位置（下标）。 由于 MEX([ap[0]])=1MEX([a_{p[0]}])=1MEX([ap[0] ])=1，所以 000 在排列 bbb 中的位置只能是 p[0]p[0]p[0]。 提示2 111 可以放在排列 bbb 中的什么位置？ 提示3 假设 p[0]<p[1]p[0] < p[1]p[0]<p[1]； 如果 p[2]<p[0]p[2] < p[0]p[2]<p[0]，222 可以放在排列 bbb 中的哪些位置？ 如果 p[2]>p[1]p[2] > p[1]p[2]>p[1]，222 可以放在排列 bbb 中的哪些位置？ 如果 p[0]<p[2]<p[1]p[0] < p[2] < p[1]p[0]<p[2]<p[1]，222 可以放在排列 bbb 中的哪些位置？ 题目解析 令 p[x]p[x]p[x] 为 xxx 在排列 aaa 中的位置（下标）。 由于 MEX([ap[0]])=1MEX([a_{p[0]}])=1MEX([ap[0] ])=1，所以 000 在排列 bbb 中的位置只能是 p[0]p[0]p[0]。 接下来讨论 111 可以放在排列 bbb 中的位置。 假设 p[0]<p[1]p[0] < p[1]p[0]<p[1]，那么 对于所有区间 [l,r](l≤p[0]<p[1]≤r)[l, r](l \le p[0] < p[1] \le r)[l,r](l≤p[0]<p[1]≤r)，有 MEX([bl,…,br])>1MEX([b_l, \ldots, b_r]) > 1MEX([bl ,…,br ])>1; 对于其他区间 [l,r](p[0]≤l≤r≤p[1])[l, r](p[0] \le l \le r \le p[1])[l,r](p[0]≤l≤r≤p[1])，有 MEX([bl,…,br])≤1MEX([b_l, \ldots, b_r]) \le 1MEX([bl ,…,br ])≤1 。 所以，111 必然只能放在 p[1]p[1]p[1] 这个位置。 我们以一个更具体的例子来说明： > 假设 p[0]<p[1]p[0] < p[1]p[0]<p[1]，不难发现以下性质: > A. 对于区间 [p[0],p[1]][p[0], p[1]][p[0],p[1]], 有 MEX([bp[0],…,bp[1]])>1MEX([b_{p[0]}, \ldots, b_{p[1]}]) > 1MEX([bp[0] ,…,bp[1] ])>1； > B. 对于区间 [p[0],x](p[0]<x<p[1])[p[0], x](p[0] < x < p[1])[p[0],x](p[0]<x<p[1])，有 MEX([bp[0],…,bx])=1MEX([b_{p[0]}, \ldots, b_{x}]) = 1MEX([bp[0] ,…,bx ])=1。 > 若 bp[1]≠1b_{p[1]} \neq 1bp[1] =1，令 xxx 为 111 在 bbb 中的位置，考虑以下两种情况： > 1. x<p[0]x < p[0]x<p[0] 或 p[1]<xp[1] < xp[1]<x: > 此时 xxx 在区间 [p[0],p[1]][p[0], p[1]][p[0],p[1]] 外，此时 MEX([bp[0],…,bp[1]])=1MEX([b_{p[0]}, \ldots, b_{p[1]}]) = 1MEX([bp[0] ,…,bp[1] ])=1 与 AAA 矛盾。 > 2. p[0]<x<p[1]p[0] < x < p[1]p[0]<x<p[1]: > 此时 xxx 在区间 [p[0],p[1]][p[0], p[1]][p[0],p[1]] 内，此时 MEX(bp[0],…,bx)>1MEX(b_{p[0]}, \ldots, b_{x}) > 1MEX(bp[0] ,…,bx )>1 与 BBB 矛盾。 将区间 [p[0],p[1]][p[0], p[1]][p[0],p[1]] 作为当前区间 [l,r][l, r][l,r] 并继续考虑 222 可以放在排列 bbb 中的位置。 若 p[2]∈[l,r]p[2] \in [l, r]p[2]∈[l,r]，那么 对于所有区间 [x,y](x≤l<r≤y)[x, y](x \le l < r \le y)[x,y](x≤l<r≤y)，有 MEX([bx,…,by])>2MEX([b_x, \ldots, b_y]) > 2MEX([bx ,…,by ])>2； 对于其他区间 [x,y](l<x≤y<r)[x, y](l < x \le y < r )[x,y](l<x≤y<r)，有 MEX([bx,…,by])≤2MEX([b_x, \ldots, b_y]) \le 2MEX([bx ,…,by ])≤2。 只要 222 在区间 [l,r][l, r][l,r] 内就能够满足以上两个条件，所以 222 可以放在区间 [l,r][l, r][l,r] 内的任何一个位置（除了已经被占用的位置），所以当 p[2]∈[l,r]p[2] \in [l, r]p[2]∈[l,r] 时，222 可以放置的位置数量为 (r−l+1)−2(r - l + 1) - 2(r−l+1)−2。 否则，222 只能放在排列 bbb 中的 p[2]p[2]p[2] 这个位置上。并且当前区间被扩展至包含 p[2]p[2]p[2]，变为 [p[2],r][p[2], r][p[2],r] 或 [l,p[2]][l, p[2]][l,p[2]]。 容易看出后续的数字 3,4,…,n−13, 4, \ldots, n - 13,4,…,n−1 都可以这样处理。 令 kkk 为当前处理的数字，若 k∈[l,r]k \in [l, r]k∈[l,r]，说明 kkk 可以放置的位置数量为 (r−l+1)−k(r - l + 1) - k(r−l+1)−k。否则将当前区间扩展至包含 p[k]p[k]p[k]。 最终问题的答案就是每个元素可以放置位置数量的乘积。 AC代码 复杂度分析 对于数字 000 可以放在排列 bbb 中的位置唯一，并可以将当前区间 [l,r][l, r][l,r] 初始化为 [p[0],p[0]][p[0], p[0]][p[0],p[0]]，之后按照顺序处理剩余的 n−1n-1n−1 个数字即可，时间复杂度为 O(n)O(n)O(n)。