Description
有这么一则传闻，O(nlogn)的排序发明之前，滋滋国的排序都是采用的冒泡排序。即使是冒泡排序，对当时的国民
来说也太复杂太难以理解，于是滋滋国出现了这样一个职业——排序使，收取报酬并负责给序列排序。作为冒泡协
会首席排序使，Lyra收费颇高，为了照顾并不富裕的人，Lyra允许顾客只支付一部分酬劳并获得并不完美的冒泡排
序服务。众所周知，n个元素的冒泡排序需要n?1n-1轮才能完成，有一位顾客支付的费用，只能够完成前k轮的排序
。作为冒泡排序的首席排序使，天赋卓绝的Lyra暗地里早就掌握了O(nlogn)的排序方法，这也是她轻松当选首席排
序使的原因——排序速度无人能敌。而现在面对只能够完成前k轮冒泡排序的要求，Lyra犯了难，于是她来寻求你
的帮助。给定一个序列，执行如下程序：
for i from 1 to k
for j from 1 to n-1
if Aj>Aj+1
swap(Aj,Aj+1)
并输出之后的A序列。
Input
第一行两个整数n,k表示序列的长度和轮数。
接下来n行每行一个整数表示Ai
1≤k<n≤200000;1≤Ai≤10^9
Output
输出n行每行一个整数表示冒泡排序k轮后的Ai
Sample Input
3 1
3
2
1
3
2
1
Sample Output
2
1
3
1
3
Solution
我把冒泡的本质想错了...然后就一直写挂样例都过不了
看了zz的题解才发现自己错的好离谱...（orzz）
事实上每次冒泡排序都会把当前数前移一位（如果前面有比它大的数的话）
用树状数组维护当前有几个比它大的
如果比它大的超过$k$个那么直接前移$k$位就好了（$k$次都有比当前大的数，移动了$k$位）
最后剩下的位置一位一位地去填，从小到大填
我怎么觉得这题主要难度在于看懂冒泡排序到底怎么做的...（
#include <bits/stdc++.h> using namespace std ; #define N 200010 #define lowbit( i ) i&(-i) int ans[ N ] , n , k , rk[ N ] , f[ N ] , c[ N ] ; struct node { int val , id ; }a[ N ] ; //每次冒泡排序都会把当前数前移一位（如果前面有比它大的数的话） //用树状数组维护当前有几个比它大的 //如果比它大的超过k个那么直接前移k位就好了（k次都有比当前大的数，移动了k位） //最后剩下的位置一位一位地去填，从小到大填 bool cmp( node a, node b ) { return a.val < b.val ; } void add( int x , int val ) { for( int i = x ; i <= n ; i += lowbit( i ) ) c[ i ] += val ; } int query( int x ) { int ans = 0 ; for( int i = x ; i ; i -= lowbit( i ) ) ans += c[ i ] ; return ans ; } int main() { scanf( "%d%d" , &n , &k ) ; for( int i = 1 ; i <= n ; i ++ ) { scanf( "%d" , &a[ i ].val ) ; a[ i ].id = i ; } sort( a + 1 , a + n + 1 , cmp ) ; rk[ a[ 1 ].id ] = 1 ; for( int i = 2 ; i <= n ; i ++ ) { if( a[ i ].val == a[ i - 1 ].val ) rk[ a[ i ].id ] = rk[ a[ i - 1 ].id ] ; else rk[ a[ i ].id ] = i ; } for( int i = 1 ; i <= n ; i ++ ) { add( rk[ i ] , 1 ) ; f[ i ] = query( n ) - query( rk[ i ] ) ; if( f[ i ] > k ) ans[ i - k ] = a[ rk[ i ] ].val ; } int cur = 1 ; for( int i = 1 ; i <= n ; i ++ ) { if( f[ a[ i ].id ] <= k ) { while( cur <= n && ans[ cur ] ) cur ++ ; ans[ cur ] = a[ i ].val ; } } for( int i = 1 ; i <= n ; i ++ ) { printf( "%d " ,ans[ i ] ) ; } return 0 ; }