CF1844F2 题解
dAniel_lele
·
·
题解
下面考虑 $c<0$ 的情况，以下设 $c'=|c|$。
首先同样可以感性理解出 $a$ 倒序可以取到最小值，然而不是最小字典序。
对于所有倒序排列后 $a_i-a_{i+1}\leq c'$ 的位置，其贡献为 $c'-(a_i-a_{i+1})$。对于所有其他位置，其贡献为 $(a_i-a_{i+1})-c'$。要想贡献不变，我们需要所有取 $(a_i-a_{i+1})-c'$ 的位置不变，剩下来分出的段一定满足第一个为段内最大值，最后一个为最小值。
考虑分成若干个段分别最优化最小字典序。贪心每一步选取最小符合要求的值。注意到一个值符合要求，当且仅当他未被选入序列的大于等于他的第一个数减去未被选入序列的小于等于他的第一个数不超过 $c'$（显然，此时我们可以在加入这个数后从大到小假如剩余的）。使用链表+线段树维护每个位置是否合法即可。总复杂度 $O(n\log n)$。
```cpp
#include <bits/stdc++.h>
#define int long long
#define mid ((l+r)>>1)
#define lowbit(i) (i&(-i))
using namespace std;
int a[1000005];
int lst[1000005],nxt[1000005],ok[1000005];
int merge(int x,int y){
if(y) return y;
else return x;
}
struct sgt{
int f[1000005];
void build(int i,int l,int r){
if(l==r){
if(ok[l]) f[i]=l;
else f[i]=0;
return ;
}
build(i*2,l,mid),build(i*2+1,mid+1,r);
f[i]=merge(f[i*2],f[i*2+1]);
}
void change(int i,int l,int r,int pos,int val){
// if(pos<l||pos>r) exit(2);
if(l==r){
f[i]=val*l;
return ;
}
if(pos<=mid) change(i*2,l,mid,pos,val);
else change(i*2+1,mid+1,r,pos,val);
f[i]=merge(f[i*2],f[i*2+1]);
}
int qry(int i,int l,int r,int ql,int qr){
if(ql>qr) exit(2);
if(ql<=l&&r<=qr) return f[i];
if(qr<=mid) return qry(i*2,l,mid,ql,qr);
if(ql>mid) return qry(i*2+1,mid+1,r,ql,qr);
return merge(qry(i*2,l,mid,ql,qr),qry(i*2+1,mid+1,r,ql,qr));
}
}tree;
int cnt=0;
void solve(){
int n,c; cin>>n>>c; for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1);
if(c>=0){
for(int i=1;i<=n;i++) cout<<a[i]<<" ";
cout<<"\n";
return ;
}
c=-c;
reverse(a+1,a+n+1);
vector<int> ans;
for(int i=1;i<=n;i++){
int j=i;
while(j<n&&a[j]-a[j+1]<=c) j++;
for(int k=i;k<=j;k++) lst[k]=k-1,nxt[k]=k+1;
lst[i]=0,nxt[j]=0;
for(int k=i;k<=j;k++) if(lst[k]==0||nxt[k]==0||(a[lst[k]]-a[nxt[k]]<=c)) ok[k]=1; else ok[k]=0;
tree.build(1,i,j);
int now=i; tree.change(1,i,j,i,0);
if(i!=j) tree.change(1,i,j,i+1,1);
lst[nxt[now]]=0;
ans.push_back(a[now]);
if(i==j) continue;
while(1){
// cout<<i<<" "<<j<<" "<<now<<"\n";
int l=i,r=j-1;
while(l<r){
int M=(l+r+1)>>1;
cnt++;
if(a[M]<a[now]-c) r=M-1;
else l=M;
}
l=min(l,j-1);
// cout<<l<<" ";
int p=tree.qry(1,i,j,i,l);
if(!p)break;
// if(p<i||p>l) exit(3);
// cout<<l<<" "<<p<<"\n";
tree.change(1,i,j,p,0);
if(lst[p]){
nxt[lst[p]]=nxt[p];
if(nxt[lst[p]]&&lst[lst[p]]){
if(a[lst[lst[p]]]-a[nxt[lst[p]]]>c) tree.change(1,i,j,lst[p],0);
}
else{
tree.change(1,i,j,lst[p],1);
}
}
if(nxt[p]){
lst[nxt[p]]=lst[p];
if(nxt[nxt[p]]&&lst[nxt[p]]){
if(a[lst[nxt[p]]]-a[nxt[nxt[p]]]>c) tree.change(1,i,j,nxt[p],0);
}
else{
tree.change(1,i,j,nxt[p],1);
}
}
ans.push_back(a[p]);
now=p;
}
ans.push_back(a[j]);
i=j;
}
if(ans.size()!=n) exit(4);
for(auto v:ans) cout<<v<<" "; cout<<"\n";
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int t; cin>>t;
while(t--) solve();
return 0;
}
```