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 翻译