F.A.Qs
Home
ProblemSet
Status
Ranklist
Contest
Login
Register
捐赠本站
Notice:
开心刷题：）
Problem 3295. -- [Cqoi2011]动态逆序对 -- 衡阳八中OJ离线版-2014-11-04
3295: [Cqoi2011]动态逆序对
Time Limit:
10 Sec
Memory Limit:
128 MB
Submit:
901
Solved:
302
[
Submit
][
Status
]
Description
对于序列A，它的逆序对数定义为满足
i
<
j
，且A
i
>A
j
的数对(
i
,
j
)的个数。给1到
n
的一个排列，按照某种顺序依次删除
m
个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数。
Input
输入第一行包含两个整数
n
和
m
，即初始元素的个数和删除的元素个数。以下
n
行每行包含一个1到
n
之间的正整数，即初始排列。以下
m
行每行一个正整数，依次为每次删除的元素。
Output
输出包含
m
行，依次为删除每个元素之前，逆序对的个数。
Sample Input
5 4
1
5
3
4
2
5
1
4
2
Sample Output
5
2
2
1
样例解释
(1,5,3,4,2)(1,3,4,2)(3,4,2)(3,2)(3)。
HINT
N<=
100000 M
<=50000
Source
[
Submit
][
Status
]
HOME
Back
