/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 700 点
問題文
(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) の転倒数とは、 整数の組 (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) の順列
- i=1,2,\dots,M-1 に対して A_i \leq A_{i+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 が行われます。操作 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 になります。
入力例 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
Score : 700 points
Problem Statement
You are given a permutation P=(P_1,P_2,\dots,P_N) of (1,2,\dots,N).
Consider the following operations k\ (k=2,3,\dots,N) on this permutation.
- Operation k: For i=1,2,\dots,k-1 in this order, if P_i > P_{i+1}, swap the values of the i-th and (i+1)-th elements of P.
You are also given a non-decreasing sequence A=(A_1,A_2,\dots,A_M)\ (2 \leq A_i \leq N) of length M.
For each i=1,2,\dots,M, find the inversion number of P after applying the operations A_1, A_2, \dots, A_i in this order.
What is the inversion number of a sequence?
The inversion number of a sequence x=(x_1,x_2,\dots,x_n) of length n is the number of pairs of integers (i,j)\ (1\leq i < j \leq n) such that x_i > x_j.Constraints
- 2 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 2 \leq A_i \leq N
- P is a permutation of (1,2,\dots,N).
- A_i \leq A_{i+1} for i=1,2,\dots,M-1.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N P_1 P_2 \dots P_N M A_1 A_2 \dots A_M
Output
Print M lines. The k-th line should contain the answer to the problem for i=k.
Sample Input 1
6 3 2 4 1 6 5 2 4 6
Sample Output 1
3 1
First, operation 4 is performed. During this, P changes as follows: (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). The inversion number of P afterward is 3.
Next, operation 6 is performed, where P eventually becomes (2,1,3,4,5,6), whose inversion number is 1.
Sample Input 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
Sample Output 2
117 116 113 110 108 105 103 99 94 87 79 72 65 58 51