1215

`2023-07-25 16:12:57 洛谷题解` # 思路 看到这道题是统计相邻交换之后操作次数，我第一反应就是求逆序对。 考虑最淳朴的暴力做法，枚举颜色之前的大小顺序关系，然后每次做一次求逆序对，复杂度 $O(n\log n |c|!)$ ($|c|$ 表示颜色种类数)。 但是光是 $20!$ ......

n个小朋友站成一排。 现在要把他们按身高从低到高的顺序排列，但是每次只能交换位置相邻的两个小朋友。 每个小朋友都有一个不高兴的程度。 开始的时候，所有小朋友的不高兴程度都是 0。 如果某个小朋友第一次被要求交换，则他的不高兴程度增加 1，如果第二次要求他交换，则他的不高兴程度增加 2（即不高兴程度为 ......