TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P2041
  • 题目
  • P2041【CQOI2011】动态逆序对
    限制 : 时间限制 : 100000 MS   空间限制 : 165536 KB
    问题描述

    对于序列A,它的逆序对数定义为满足i<j,且Ai>Aj的数对(i,j)的个数。给1到n的一个排列,按照某种顺序依次删除m个元素,你的任务是在每次删除一个元素之前统计整个序列的逆序对数。

    输入格式

    输入第一行包含两个整数n和m,即初始元素的个数和删除的元素个数。以下n行每行包含一个1到n之间的正整数,即初始排列。以下m行每行一个正整数,依次为每次删除的元素。

    输出格式

    输出包含m行,依次为删除每个元素之前,逆序对的个数。

    样例输入

    5 4
    1
    5
    3
    4
    2
    5
    1
    4
    2

    样例输出

    5
    2
    2
    1

    提示

    样例解释
    (1,5,3,4,2)>>(1,3,4,2)>>(3,4,2)>>(3,2)>>(3)。


    数据范围
    编号 1-2 3-4 5-6 7-8 9-10
    n <=1000 <=30000 <=50000 <=60000 <=100000
    m <=100 <=10000 <=20000 <=40000 <=50000