题目描述
Bessie把快速排序和冒泡排序混在了一起
给一个伪快排的代码：
冒泡：
bubble_sort_pass (A) {
for i = to length(A)-
if A[i] > A[i+], swap A[i] and A[i+]
}
“快排”：
quickish_sort (A) {
if length(A) = , return
do { // Main loop
work_counter = work_counter + length(A)
bubble_sort_pass(A)
} while (no partition points exist in A)
divide A at all partition points; recursively quickish_sort each piece
}
代码解释：
设大小为i的数为ai，定义i是分割点，当且仅当当前序列中，小于ai的数都在i左边，大于ai的数都在i右边。
每一次对于当前层的当前区间进行冒泡排序。
直到找到 一个这样的分割点为止。（一次性可能出来多个）
然后对与每个分割点分割成若干个小区间。递归下去。
A长度为1的时候，直接返回
work_counter是一个计数器。
题目给一个序列，求排好序，计数器的值是多少。
n<=100000,ai<=1e9
题解：
发现分割点的定义和上一个题的最后排序停止的条件很类似。
还是考虑什么时候排序会停止。
也就是所有的 位置i都是分割点了。
直接算A长度不好算。
那么就算每个位置i一共被加了几次。
设t[i]表示i位置出现分割点的时间（即i位置已经被算了几次）
这里，i是n+1个端点编号了注意。
那么，位置i计算的次数，就是max(t[i],t[i+1])
所有位置计算次数的和就是ans
ti怎么算
发现对于这个一般的冒泡排序，上一个题也说了
i之后比i小的数会以每次1个单位的速度往i走。
所以，i位置出现分割点的时间，必然是最晚的i之后的数到达i的次数。
其实每一次循环，因为最大数会沉底，那么一次就会出现至少一个分割点的。然后就break递归下去了
而每一次，位置i前面一个格子的长度会被算一次，i后面一个格子长度会被算一次。
那么，t[i]也就是i格子或者i+1格子的至少的贡献了。
具体来说，离散化之后，求所有的小于等于i的数到i的距离（i位置之前的不算）。
用一个变量记录maxpos即可。
对于数字a，b相同？
那么，靠后的数字b，最终一定在a的后面。就相当于b比a大了。
所以可以在离散化的时候不要unique，然后开一个桶，记录出现次数即可。
O（n）
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=+;
int n;
int a[N],b[N],p[N];
int cnt[N];
int tim[N];
long long ans;
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i];
sort(b+,b+n+);
for(int i=;i<=n;i++){
int t=lower_bound(b+,b+n+,a[i])-b;
int lp=t+cnt[t];
cnt[t]++;t=lp;
p[t]=i;
}
int maxpos=;
for(int i=;i<=n;i++){
maxpos=max(maxpos,p[i]);
tim[i]=max(,maxpos-i);
}
for(int i=;i<=n;i++){
ans+=max(tim[i],tim[i-]);
}printf("%lld",ans);return ;
}