P3157 [CQOI2011]动态逆序对

    • 686通过
    • 2.7K提交
  • 题目提供者 洛谷OnlineJudge
  • 评测方式 云端评测
  • 标签 主席树 分治 树状数组 2011 重庆 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

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

    输入输出格式

    输入格式:

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

    输出格式:

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

    输入输出样例

    输入样例#1: 复制
    5 4
    1
    5
    3
    4
    2
    5
    1
    4
    2
    输出样例#1: 复制
    5
    2
    2
    1
    
    样例解释
    (1,5,3,4,2)(1,3,4,2)(3,4,2)(3,2)(3)。

    说明

    N<=100000 M<=50000

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。