[校内训练19_09_06]排序

题意

一个这样的算法：

int cnt=0;
for(int i=1;i<=n;++i)
{
    for(int j=i+1;j<=n;++j)
    {
        if(a[j]<a[i])
        swap(a[j],a[i]);
        ++cnt;
    }
}

现在你cnt和原始数组a，求cnt步数后a的结果。注意a是n排列。

$1 leq n leq 10^6,1 leq cnt leq frac{n(n-1)}{2}$

思考

对于某个i，如果j从i+1循环到了n，那么含义就是将i~n中最小的数放到第i位上，剩下的访问过的向右循环位移一位（在访问过的数中循环位移）。

如果说外层的i在1~k中都完全遍历了一边，那么含义就是将1~k放到最前面。

如果我们从小到大依次插入数字i，可以发现，最后每个数字的相对位置是不会改变的。

这样，我们模拟这个过程。首先确定每个数的位置在哪，将大小位1~k的位置扔到大根对中。接下来从k+1枚举到n，若数字i的位置比堆顶靠后，那么这个数的位置就不会有变化（因为比它小的数都在它之前）。否则这个数最后就会到堆顶的位置（注意是从k+1枚举到n，从小到大），将对顶弹出，把数字i的位置加入。

最后将剩下的步数处理了。

复杂度$O(nlogn)$

代码

// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int maxn=1E6+5;
int n,a[maxn],b[maxn],where[maxn];
ll cnt;
void solve(int x)
{
    if(x==0)
        return;
    priority_queue<int>Q;
    for(int i=1;i<=n;++i)
        where[a[i]]=i;
    for(int i=1;i<=x;++i)
    {
        b[i]=i;
        Q.push(where[i]);
    }
    for(int i=x+1;i<=n;++i)
    {
        if(where[i]>Q.top())
            b[where[i]]=i;
        else
        {
            b[Q.top()]=i;
            Q.pop();
            Q.push(where[i]);
        }
    }
    for(int i=1;i<=n;++i)
        a[i]=b[i];
}
int main()
{
//    freopen("sort.in","r",stdin);
//    freopen("sort.out","w",stdout);
    ios::sync_with_stdio(false);
    cin>>n>>cnt;
    for(int i=1;i<=n;++i)
        cin>>a[i];
    for(int i=1;i<=n;++i)
    {
        if(cnt<=n-i)
        {
            solve(i-1);
            for(int j=i+1;j<=n;++j)
            {
                if(a[j]<a[i])
                    swap(a[j],a[i]);
                --cnt;
                if(cnt==0)
                {
                    for(int k=1;k<=n;++k)
                        cout<<a[k]<<" ";
                    cout<<endl;
                    return 0;
                }
            }
        }
        else
            cnt-=n-i;
    }
    return 0;
}