P3149 排序

    • 2通过
    • 4提交
  • 题目提供者 一UNowen一
  • 评测方式 云端评测
  • 标签 树状数组 洛谷原创 高性能
  • 难度 尚无评定
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目背景

    有 n 个人依次站在小 A 面前。小 A 会依次对这 n 个人进行 m 次操作。

    题目描述

    每次操作选择一个位置 k,将这 n 个人中的所有身高小于等于当前 k 位置的 人的身高的人从队伍里拎出,然后按照身高从矮到高的顺序从左到右依次插入到 这些人原本的位置当中。

    小 A 对这 n 个人身高构成的序列的逆序对很感兴趣。现在小 A 想要知道每一 次操作后这个序列的逆序对数。

    输入输出格式

    输入格式:

    第一行 2 个整数 n 和 m,表示人数和操作数。

    接下来一行 n 个整数 ai,表示初始状态从左到右每个人的身高。

    接下来 m 行每行 1 个数,表示这次操作的 k

    输出格式:

    输出共 m+1 行,第 1 行表示未操作时的逆序对数量。

    除第一行外第 i 行表示第 i-1 次操作后序列的逆序对数。

    输入输出样例

    输入样例#1: 复制
    5 2
    1 5 3 4 2
    3
    4
    输出样例#1: 复制
    5
    4
    3

    说明

    第一次操作后序列为1 5 2 4 3

    第二次操作后序列为1 5 2 3 4

    对于100%的数据,n,m≤300000,1≤k≤n,,1≤ai≤10^9

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