分数: 700 点
问题陈述
给你一个排列 P=(P_1,P_2,\dots,P_N) of (1,2,\dots,N).
考虑以下操作 k\ (k=2,3,\dots,N) 在此排列上。
- 操作 k:对于 i=1,2,\dots,k-1 按此顺序,如果 P_i > P_{i+1},交换的值 i-th 和 (i+1)第一个元素 P.
您还获得了 非递减 序列 A=(A_1,A_2,\dots,A_M)\ (2 \leq A_i \leq N) 长度 M.
对于每个 i=1,2,\dots,M,求倒数 P 应用操作后 A_1, A_2, \dots, A_i 按此顺序。
什么是序列的反转数?
序列的反转数 x=(x_1,x_2,\dots,x_n) 长度 n 是整数对的数量 (i,j)\ (1\leq i < j \leq n) 这样 x_i > x_j.约束
- 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).
- A_i \leq A_{i+1} 为 i=1,2,\dots,M-1.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N P_1 P_2 \dots P_N M A_1 A_2 \dots A_M
输出
打印 M 行。的 k- 第行应包含问题的答案 i=k.
示例输入 1
6 3 2 4 1 6 5 2 4 6
示例输出 1
3 1
一、操作 执行 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)。的反转数为 P 之后是 3.
接下来,操作 执行 6 ,其中 P 最终变成 (2,1,3,4,5,6),其反转数为 1.
示例输入 2
20 12 14 16 8 7 15 19 6 18 5 13 9 10 17 4 1 11 20 2 3 15 3 4 6 8 8 9 10 12 13 15 18 18 19 19 20
示例输出 2
117 116 113 110 108 105 103 99 94 87 79 72 65 58 51