Pair Swap [CSAcademy #54]

https://csacademy.com/contest/round-54/task/pair-swap/

N個の配列Aがある。
この配列に対し、距離がK以内の任意の1ペアをswapできる(しなくてもいい)。
作れる辞書順最小の配列を答えよ。

K≦N≦10^5

前提知識

• セグメントツリーの知識

解説

これは先頭からなるべく小さくしていけば辞書順最小となるので、先頭から貪欲にswap先を探してくればいい。
i番目をswapするのは、[i+1,i+K]にA[i]よりも小さい要素があるときである。
これは区間minのセグメントツリーを使えばいい。
swapする必要があるので、セグメントツリーにpairを乗せて、添字も取ってこれるようにする。
あと、最小値が複数ある場合はなるべく後ろにある要素とswapしたいので、pairの標準minをするなら、添字部分を負にして持っておくと最小値が複数ある場合は後ろにある要素を取ってこれる。

#define INF INT_MAX/2
#define def make_pair(INF,INF)
template<class V, int NV> struct SegTree { //[l,r)
    V comp(V& l, V& r) { return min(l,r); };
    vector<V> val; SegTree() { val = vector<V>(NV * 2, def); }
    V get(int x,int y,int l=0,int r=NV,int k=1){if(r<=x||y<=l)return def;if(x<=l&&r<=y)return val[k];
    auto a=get(x,y,l,(l+r)/2,k*2);auto b=get(x,y,(l+r)/2,r,k*2+1);return comp(a,b);}
    void update(int i, V v) { i+=NV;val[i]=v;while(i>1)i>>=1,val[i]=comp(val[i*2],val[i*2+1]); }
    void add(int i, V v) { update(i, val[i + NV] + v); }};





int N, K, A[101010];
SegTree<pair<int, int>, 1 << 17> st;
//---------------------------------------------------------------------------------------------------
void solve() {
    rep(i, 0, N) st.update(i, { A[i], -i });

    rep(i, 0, N) {
        auto p = st.get(i + 1, min(i + K + 1, N));
        if (p.first < A[i]) {
            swap(A[i],A[-p.second]);
            return;
        }
    }
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    rep(i, 0, N) cin >> A[i];

    solve();

    rep(i, 0, N) {
        if (i) printf(" ");
        printf("%d", A[i]);
    } printf("\n");
}