← 返回题目列表

AtCoder · arc181_d

D. 前缀冒泡排序

中文机器翻译题面 查看原题

分数: 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