【分治记录】[AGC001F] Wide Swap

wgyhm · 2021-11-11 10:56:16 · 题解

大概是对 FrSmT 题解的补充说明。

Description

给出一个元素集合为 \{1,2,3,...,N\} 排列 P，当且仅当存在 1\le i\le j\le N,j-i\ge K,|P_i-P_j|=1 时，可以交换 P_i,P_j。

求可能的排列中字典序最小的排列。

1\le N\le 5\times 10^5

Solution

观察题目，当 P_j-P_i=1 的时候，交换后字典序变小，逆序对减 1。

令 Q_i 表示 i 在 P 中的位置，Q_{p_i}=i。

问题转化为：

当且仅当 Q_i-Q_{i+1}\ge K 时交换 Q_i,Q_{i+1}。
重复上述操作，直到无法操作。
求 Q。

注意到 K=1 时，就是排序。所以显然有一个 O(n^2) 的冒泡排序算法。

考虑分治优化，类似于归并排序。Q[l...mid] ，Q[mid+1...r] 两个子序列都满足 Q_i-Q_{i+1}<K

现在只需要在可以接受的复杂度内合并两个序列即可。

考虑两个不相邻的 Q_i,Q_j,i<j 如果可以让 Q_j 到 Q_i 的位置且使原序列更优，当且仅当 \min _{l=i}^{j-1} Q_l\ge Q_j+K

大概的意思如下（数字表示原来的下标） :

i i+1 i+2 i+3 ... j-1 j

因为 Q_{j-1}-Q_j\ge K ，所以可以交换 Q_{j-1},Q_j。

然后新的 Q_{j-2}-Q_{j-1}\ge K 。。。以此类推，变成：

j i i+1 i+2 ... j-2 j-1

维护左区间的后缀最小值。如果满足上述条件，则把右区间的第一个元素加入队列，注意到左区间剩下的元素集体向右移了一位，所以 \min _{l=i}^{j-1} Q_l 还是不变的。否则把左区间的第一个元素加入队列。

Code

#include<bits/stdc++.h>
#define rg register
#define ll long long 
#define maxn 500005
#define put() putchar('\n')
using namespace std;
inline void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
int n,K,a[maxn],g[maxn];
int t[maxn],Min[maxn];
inline void solve(int l,int r){
    if (l==r) return;
    int mid=l+r>>1,i,j,k;
    solve(l,mid);
    solve(mid+1,r);
    Min[mid]=a[mid];
    for (i=mid-1;i>=l;i--) Min[i]=min(Min[i+1],a[i]);
    i=l,j=mid+1,k=l-1;
    while (i<=mid&&j<=r) {
        if (Min[i]>=a[j]+K) t[++k]=a[j],j++;
        else t[++k]=a[i],i++;
    }
    while (i<=mid) t[++k]=a[i],i++;
    while (j<=r) t[++k]=a[j],j++;
    for (i=l;i<=r;i++) a[i]=t[i];
}
signed main(){
    rg int i;
    read(n);read(K);
    for (i=1;i<=n;i++) read(g[i]),a[g[i]]=i;
    solve(1,n);
    for (i=1;i<=n;i++) g[a[i]]=i;
    for (i=1;i<=n;i++) printf("%d\n",g[i]);
    return 0;
}