AT_arc181_d.[ARC181D] Prefix Bubble Sort

给定一个 $ (1,2,\dots,N) $ 的排列 $ P=(P_1,P_2,\dots,P_N) $。

对于该排列，定义如下操作 $ k\ (k=2,3,\dots,N) $：

• 操作 $ k $：依次对 $ i=1,2,\dots,k-1 $，如果 $ P_i > P_{i+1} $，则交换 $ P $ 的第 $ i $ 项和第 $ i+1 $ 项的值。

给定一个长度为 $ M $ 的广义单调递增数列 $ A=(A_1,A_2,\dots,A_M)\ (2 \leq A_i \leq N) $。

对于每个 $ i=1,2,\dots,M $，请你求出对 $ P $ 依次按顺序执行操作 $ A_1,A_2,\dots,A_i $ 后，排列 $ P $ 的逆序对数。

数列的逆序对数定义如下：对于长度为 $ n $ 的数列 $ x=(x_1,x_2,\dots,x_n) $，逆序对数是满足 $ 1 \leq i < j \leq n $ 且 $ x_i > x_j $ 的整数对 $ (i,j) $ 的个数。

输入以如下格式从标准输入读入：

$ N $ $ P_1 $ $ P_2 $ $ \dots $ $ P_N $ $ M $ $ A_1 $ $ A_2 $ $ \dots $ $ A_M $

输出 $ M $ 行。第 $ k $ 行输出 $ i=k $ 时的答案。

限制条件

• $ 2 \leq N \leq 2 \times 10^5 $
• $ 1 \leq M \leq 2 \times 10^5 $
• $ 2 \leq A_i \leq N $
• $ P $ 是 $ (1,2,\dots,N) $ 的一个排列
• 对于 $ i=1,2,\dots,M-1 $，有 $ A_i \leq A_{i+1} $
• 所有输入的值均为整数

样例解释 1

首先执行操作 $ 4 $。在操作 $ 4 $ 的过程中，$ P $ 依次变为 $ (3,2,4,1,6,5)\rightarrow(2,3,4,1,6,5)\rightarrow(2,3,4,1,6,5)\rightarrow(2,3,1,4,6,5) $。操作 $ 4 $ 结束后，$ P $ 的逆序对数为 $ 3 $。接着执行操作 $ 6 $，$ P $ 最终变为 $ (2,1,3,4,5,6) $，逆序对数为 $ 1 $。

由 ChatGPT 4.1 翻译