P3157 [CQOI2011] Dynamic Inversions

For a sequence $a$, its number of inversions is defined as the size of the set $$\{(i,j)\mid i a_j \}.$$ You are given a permutation of $1\sim n$. According to some order, $m$ elements are deleted one by one. Your task is to count the number of inversions of the entire sequence before each deletion.

The first line contains two integers $n$ and $m$, which are the initial number of elements and the number of deletions. The next $n$ lines each contain a positive integer between $1 \sim n$, which is the initial permutation. Then the next $m$ lines each contain a positive integer, in order, which is the element to delete at each step.

Output $m$ lines, where the $i$-th line is the number of inversions before deleting the $i$-th element.

Constraints For $100\%$ of the testdata, $1 \le n \le 10^5$, $1 \le m \le 50000$. Sample Explanation The sequences before each deletion are: $$1,5,3,4,2$$ $$1,3,4,2$$ $$3,4,2$$ $$3,2$$ Translated by ChatGPT 5