题解 [USACO22JAN] Minimizing Haybales P

· · 题解

题意：给一个长度为 N 的数组 a ，若相邻两数之差的绝对值不超过 K 则可以交换，问能得到的所有 a 中字典序最小的一个。

数据范围：1\le N,K\le 10^5,1\le a_i\le 10^9

发现 |a_i-a_j| > K 的数无法交换，于是这两个数的相对位置是固定的。换言之，不妨设 i<j ，那么 a_i 始终会在 a_j 前面。对于所有这样的 (i,j) ，我们将 i 向 j 连一条有向边，按照题目要求做拓扑排序即可。

如何做？正常最小拓扑序是把所有入度为 0 的点放入优先队列中，然后每次取堆顶的点并将其连出的边删除。时间复杂度为 O(NK) ，瓶颈为图中可能的边数。

思考一下如何优化，首先可以对原数组离散化，用一个线段树来维护当前可能的最小位置，每次取出作为答案并更新与其有连边的点的入度即可。具体地，若当前点的权值为 u ，则 [1,m]\setminus[u-K+1,u+K-1] 中的所有权值对应的点的入度 -1 。需要一个带懒标记线段树做区间更新。

时间复杂度：O(N\log N)

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define pii pair<int,int>
#define vi vector<int>
#define fi first
#define se second
#define pb push_back
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define ALL(x) x.begin(),x.end()
#define sz(x) int(x.size())
#define ll long long
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
const int N=2e5+5;
int n,K,a[N],val[N],deg[N];
unordered_map <int,int> vis;
#define ls (p<<1)
#define rs (ls|1)
#define mid ((L+R)>>1)
pii t[N<<2];
int tag[N<<2];
inline pii Min(const pii a,const pii b){
    if(a.se == b.se)return make_pair(min(a.fi,b.fi),a.se);
    return a.se < b.se ? a : b;
}
void build(int p,int L,int R){
    if(L == R){
        t[p] = make_pair(L,deg[L]);
        return;
    }
    build(ls,L,mid),build(rs,mid+1,R);
    t[p] = Min(t[ls],t[rs]);
}
void push(int p,int v){tag[p] += v,t[p].se += v;}
void down(int p){
    if(!tag[p])return;
    push(ls,tag[p]),push(rs,tag[p]);
    tag[p] = 0;
}
void upd(int p,int L,int R,int l,int r,int v){
    if(l > R || r < L)return;
    if(l <= L && R <= r){
        push(p,v);
        return;
    }
    down(p);
    upd(ls,L,mid,l,r,v),upd(rs,mid+1,R,l,r,v);
    t[p] = Min(t[ls],t[rs]);
}
int T[N];
void add(int x){for(;x <= n;x += x & -x)T[x]++;}
int Q(int x){
    int res = 0;
    for(;x;x -= x & -x)res += T[x];
    return res;
} 
int main(){
    n = read(),K = read();
    rep(i,1,n)a[i] = read(),val[i] = a[i];
    sort(val+1,val+n+1);
    rep(i,1,n){
        vis[a[i]]++;
        a[i] = lower_bound(val+1,val+n+1,a[i]) - val + vis[a[i]] - 1;
    }
    //calculating in-degree
    rep(i,1,n){
        int x = lower_bound(val+1,val+n+1,val[a[i]]-K) - val - 1;
        int y = lower_bound(val+1,val+n+1,val[a[i]]+K+1) - val - 1;
        deg[a[i]] = (i-1) + Q(x) - Q(y);
        add(a[i]);
    }
    build(1,1,n);
    rep(i,1,n){
        int u = t[1].fi;
        cout << val[u] << '\n';
        int x = lower_bound(val+1,val+n+1,val[u]-K) - val - 1;
        //cout << 1 << ' ' << x << '\n';
        int y = lower_bound(val+1,val+n+1,val[u]+K+1) - val - 1;
        //cout << y+1 << ' ' << n << '\n';
        //cout << u << ' ' << u << '\n';
        upd(1,1,n,1,x,-1);
        upd(1,1,n,y+1,n,-1);
        upd(1,1,n,u,u,n);
    }
    return 0;
}