TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P2041
  • 問題
  • P2041【CQOI2011】动态逆序对
    制限 : 時間制限 : 100000 MS   メモリ制限 : 165536 KB
    審判説明 : 2s
    問題説明

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

    \(n<=100000\)
    \(m<=50000\)

    入力形式

    输入第一行包含两个整数$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