排山倒海气贯长虹风中残烛独树一帜另辟蹊径首届艾特寇德格兰达比赛最终题题解

linghuchong_ · 2021-10-10 20:43:43 · 题解

一种新的思路。

考虑构造序列 Q 使得 Q_{P_i}=i，变成交换相邻的差值大于等于 k 的数。

先考虑暴力做法，按照冒泡排序，把大的尽可能往右挪。

然后把冒泡排序改为归并排序。一个右边的数能比左边的数先进行归并就要保证它加 k 小于等于左边的数的后缀最小值即可。每次归并时记录左边的后缀最小值。

代码如下

#include<bits/stdc++.h>
#define FOR(i,a,b) for(register int i=a;i<=b;i++)
#define ROF(i,a,b) for(register int i=a;i>=b;i--)
#define isnum(ch) ('0'<=ch&&ch<='9')
#define int long long
#define gc (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
char buf[100000],*p1(buf),*p2(buf);
using namespace std;
inline int read()
{
    int s=0,f=1;char _ch=gc;
    while(!isnum(_ch))(_ch=='-')&&(f=-1),_ch=gc;
    while(isnum(_ch))s=s*10+_ch-48,_ch=gc;
    return s*f;
}
const int N=5e5+10;
int n,k,a[N],id[N];
int Min[N],b[N];
#define mid ((l+r)>>1)
void merge(int l,int r){
    if(l==r)return;
    merge(l,mid),merge(mid+1,r);
    int num=N,now1=l,now2=mid+1,cnt=l;
    ROF(i,mid,l)num=min(num,a[i]),Min[i]=num;
    while(now1<=mid&&now2<=r){
        if(Min[now1]>=a[now2]+k)b[cnt++]=a[now2],now2++;
        else b[cnt++]=a[now1],now1++;
    }
    while(now1<=mid)b[cnt++]=a[now1],now1++;
    while(now2<=r)b[cnt++]=a[now2],now2++;
    FOR(i,l,r)a[i]=b[i];
}
signed main()
{
    n=read(),k=read();
    FOR(i,1,n)a[read()]=i;
    merge(1,n);
    FOR(i,1,n)id[a[i]]=i;
    FOR(i,1,n)cout<<id[i]<<'\n';
    return 0;
}