[NOI Online #1 提高组] 冒泡排序 小结

naive 想法：

以每个前缀最大值为端点分组，每组第一个数是前缀最大值

容易发现第一次冒泡排序就是对这些前缀最大值从组头到组尾，然后每次减少的逆序对数量就是组内元素-1

误以为每次冒泡排序后前缀最大值不会增多，发现每一次冒泡排序，分组变化就是最前面的一组消失，其他的组虽然位置不同但是长度于之前等价。

所以变成了这样一个问题：给你一些数，第 i 个数可以存活 i 秒，第 i 个数存活一秒有 wi 的贡献，问 \(k\) 秒后总贡献。

考虑到修改问题，分类讨论一下，发现每次最多增加/减少一个分组，增加的位置可以实时维护一下前缀最大值然后二分出来。数据结构维护一下存活时间后，算算贡献即可

虽然整体想错了，但是算这个的贡献的部分是想对了的，涉及到一坨数据结构，锻炼了对于数据结构的理解和应用

反思：

发现失误在于没有考虑到一次冒泡排序后前缀最大值个数会增加

本质上，是对所谓”前缀最大值“条件的转化不够深入，应转化到 b[i]= 前面比 ai 大的数的个数 的变化，然后才能分析问题

在关注点投入到 \(b_i\) 后，出现了两种思路

一种是从整体看，发现每次冒泡排序减少的逆序对个数就是（n- \sum[b[i]=0]) ，发现数 i 会在时刻 b[i]+1 变成前缀最大值，即 \(b[i]=0\) 。b[i] 变成 0 之后就不会变了。所以直接维护 ans[x] 表示进行 x 轮冒泡排序的答案，i 的贡献相当于 ans[b[i]...n]-1。考虑修改，发现每次修改会使得初始逆序对数 +-1，而因为本来在时刻 b[i] 就会使得逆序对数做出这样的变化，所以把后面的 -+1

一种延续不直接维护 ans 的思路，发现每次 b[i]=max(b[i+1]-1,0) ，维护即可，维护方法比较高级。

所以，问题出在条件转化的不够深入，细节思考的想当然，以及没有从整体角度看问题（每次减少的逆序对数量就是组内元素-1 \to 冒泡排序减少的逆序对个数就是（n- \sum[b[i]=0]) ）

一定要手模样例。

c，写完总结之后觉得这道题突然 sb 起来了。

本题（包括写总结）大概用时 2h