\(\text{Luogu8099}\)
题目描述
现在有一个长度为 \(n\) 的序列 \(\{h\}\) 。定义一次操作为选择两个 相邻 下标 \(i,j\) ，若 \(|h_i-h_j|\leqslant k\) 就交换 \(h_i,h_j\) 。你可以进行上述操作无数次。
问可以得到的最小字典序序列是什么？
\(n \leqslant 10^5\) 。
思路点拨
不论你如何操作，如果两个位置 \(i,j\) 有 \(|h_i-h_j|>k\) 那么 \(h_i,h_j\) 的相对位置关系是不会变得，别的我们显然可以任意变动。最终我们需要在保持若干个相对位置关系的前提下让字典序最小不难想到一个暴力：
-
对于 \(i,j(i<j)\) ，如果 \(|h_i-h_j|>k\) 我们就让 \(i\) 向 \(j\) 连有向边。
-
所以一个答案对应了有向图上的一个拓扑序，我们希望这个拓扑序字典序尽可能的小直接将拓扑排序的队列换成堆即可。
时间复杂度上界 \(O(n^2\log n)\) 。
考虑进行优化，我们连边的方式的关系比较特殊，对于节点 \((i,h_i)\) 向 \((j,h_j)\) 连边的前提就是 \(j>i\) 并且 \(h_j \notin [h_i-k,h_i+k]\) 。一开始我们可以简单求出对于一个节点 \(i\) 他在有向图中的入度是多少。
拓扑排序的过程中我们每取出一个节点就将满足 \(j>i\) 并且 \(h_j \notin [h_i-k,h_i+k]\) 的节点入度减一，使用树套树做到 \(O(n \log^2 n)\) ，已经足够通过本题。
我们发现树套树没有必要维护 \(j>i\) 的关系，因为如果对于节点 \(i\) 他在入度的边全部被删除的情况下，存在 \(j<i\) 并且 \(h_j \notin [h_i-k,h_i+k]\) 这个与我们的假设是矛盾的。故没有必要维护下标。时间优化到 \(O(n \log n)\) 。
代码实现时离散化会更加方便。
#include<bits/stdc++.h>
#define int long long
#define lowbit(x) ((x)&(-x))
using namespace std;
namespace IO{
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline void print(int x){
if(x>9) print(x/10);
putchar(x%10+'0');
}
}
using namespace IO;
const int MAXN=1e5+10,inf=1e9;
int n,k;
int a[MAXN],deg[MAXN],tmp[MAXN];
map<int,int> vis;
int bit[MAXN];
void add(int x){
for(int i=x;i<=n;i+=lowbit(i)) bit[i]++;
}
int query(int l,int r){
int cnt=0;
for(int i=r;i;i-=lowbit(i)) cnt+=bit[i];
for(int i=l-1;i;i-=lowbit(i)) cnt-=bit[i];
return cnt;
}
struct node{
int x,y;
node(int x_=0,int y_=0){x=x_,y=y_;}
}t[MAXN<<2];
int tag[MAXN<<2];
void pushup(int i){
if(t[i<<1].y==t[i<<1|1].y)
t[i]=node(min(t[i<<1].x,t[i<<1|1].x),t[i<<1].y);
else t[i]=(t[i<<1].y<t[i<<1|1].y)?t[i<<1]:t[i<<1|1];
}
void pushdown(int i){
t[i<<1].y+=tag[i],t[i<<1|1].y+=tag[i];
tag[i<<1]+=tag[i],tag[i<<1|1]+=tag[i];
tag[i]=0;
}
void build(int i,int l,int r){
if(l==r){
t[i]=node(l,deg[l]);
return ;
}
int mid=(l+r)>>1;
build(i<<1,l,mid),build(i<<1|1,mid+1,r);
pushup(i);
}
void update(int i,int l,int r,int L,int R,int w){
if(l>R||r<L) return ;
if(L<=l&&r<=R){
t[i].y+=w,tag[i]+=w;
return ;
}
int mid=(l+r)>>1;
pushdown(i);
update(i<<1,l,mid,L,R,w);
update(i<<1|1,mid+1,r,L,R,w);
pushup(i);
}
signed main(){
n=read(),k=read();
for(int i=1;i<=n;i++)
a[i]=tmp[i]=read();
sort(tmp+1,tmp+n+1);
for(int i=1;i<=n;i++){
vis[a[i]]++;
a[i]=lower_bound(tmp+1,tmp+n+1,a[i])-tmp-1+vis[a[i]];
}
for(int i=1;i<=n;i++){
int w=tmp[a[i]];
int L=lower_bound(tmp+1,tmp+n+1,w-k)-tmp,R=upper_bound(tmp+1,tmp+n+1,w+k)-tmp-1;
deg[a[i]]=(i-1)-query(L,R);
add(a[i]);
}
build(1,1,n);
for(int i=1;i<=n;i++){
int w=t[1].x;
print(tmp[w]),putchar('\n');
int L=lower_bound(tmp+1,tmp+n+1,tmp[w]-k)-tmp,R=upper_bound(tmp+1,tmp+n+1,tmp[w]+k)-tmp-1;
if(L>1) update(1,1,n,1,L-1,-1);
if(R<n) update(1,1,n,R+1,n,-1);
update(1,1,n,w,w,inf);
}
return 0;
}