第二回全国統一プログラミング王決定戦予選 C - Swaps

自分のコンテスト中の思考過程に沿って書きますが，公式解説の方がシンプルで高速に解けると思います．というか未証明です．

まず， $(A_i, B_i)$ のペアを並び替えて $B_i$ が昇順になるようにする．この操作をしても一般性を失わない．

最も大きい $A_i$ に着目する． $A_i \gt B_i$ を直す場合， $B_j \geq A_i$ であるような $A_j$ のうちいずれかとswapを行う． $B_i$ に対応する $A_j$ は $B_i$ 以下のものでなければならないので， $A_j$ のうち最小のものを選ぶべきである．この操作を行うと最も大きい $A_i$ については $A_i \leq B_i$ が確定する．したがって次に大きい $A_i$ について同様の操作を行えばいい．
この操作を繰り返し行い，「 $A_i \leq B_i$ 」「swap回数が $N-2$ 回以下」の条件を満たすか？を確認すればよい．

サンプル3にこの操作を適用してみる．最初に最も大きい $A_3=6$ に着目する．区間 $\lbrack 5,6)$ で最も小さいものは $A_5=2$ なので， $A_3$ と $A_5$ をswapする．次に大きい $A_2=4$ に着目する．区間 $\lbrack 4,6)$ で最も小さいものは $A_4=3$ なので， $A_2$ と $A_4$ をswapする．同様に考えると $A_1$ と $A_3$ をswapすればよい．
交換を行ったあとは $A_i \leq B_i$ になっており，交換回数が3回なので "Yes" と判定される．

i: 012345   012345   012345   012345  
a: 134632 → 134236 → 133246 → 123346  
b: 223348 → 223348 → 223348 → 223348

swapを何回でもしていいときに $A_i \leq B_i$ にできる場合，上述の操作で $A_i \leq B_i$ にすることが可能である．swap回数が本当は $N-2$ 回以下であるのに上述の操作で $N-1$ 回になってしまうような数列が存在すると，誤判定をしてしまう．
上述の操作で交換回数が $N-1$ 回になってしまうような数列を考える．以下のような最小の $A_i$ が毎回swapの対象に選ばれるものなど，公式解説の置換が1つのサイクルであるようなものだけなので（これ本当か？未証明）誤判定をすることはない．

a: 34562  
b: 23458

区間minを求めるのにセグ木， $A_i$ を降順に見るのにmultiset等を使って操作のシミュレーションを行うことで解けた．

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll, ll>;  
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
#define ALL(x) x.begin(), x.end()  
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }  
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
#ifdef DEBUG_   
#include "../program_contest_library/memo/dump.hpp"  
#else  
#define dump(...)  
#endif  
const ll INF = 1LL<<60;  
  
  
// 根が1 !!!!!  
template<typename Monoid>  
struct segtree {  
    using T = typename Monoid::T;  
    int n;  
    vector<T> dat;  
  
    segtree(int n_) {  
        n = 1;  
        while(n < n_) n <<= 1;  
        dat.assign(n*2, Monoid::id());  
    }  
    void build(vector<T> v) {  
        REP(i, v.size()) dat[i+n] = v[i];  
        for(int i=n-1; i>0; --i) dat[i] = Monoid::op(dat[i*2], dat[i*2+1]);  
    }  
  
    T query(int a, int b) {  
        T l = Monoid::id(), r = Monoid::id();  
        for(a+=n, b+=n; a<b; a>>=1, b>>=1) {  
            if(a&1) l = Monoid::op(l, dat[a++]);  
            if(b&1) r = Monoid::op(dat[--b], r);  
        }  
        return Monoid::op(l, r);  
    }  
    void update(int i, T v) {  
        i += n;  
        dat[i] = v;  
        while(i >>= 1) {  
            dat[i] = Monoid::op(dat[i*2], dat[i*2+1]);  
        }  
    }  
  
    friend ostream &operator <<(ostream& out,const segtree<Monoid>& seg){  
        out << "---------------------" << endl;  
        int cnt = 1;  
        for(int i=1; i<=seg.n; i*=2) {  
            REP(j, i) {  
                out << seg.dat[cnt] << " ";  
                cnt++;  
            }  
            out << endl;  
        }  
        out << "---------------------" << endl;  
        return out;  
    }  
};  
  
template<typename Tp>  
struct min_monoid {  
    using T = Tp;  
    static constexpr Tp id() { return PII(INF, INF); }  
    static Tp op(const Tp &a, const Tp &b) { return min(a, b); }  
};  
  
int main(void) {  
    ll n;  
    cin >> n;  
    vector<PII> p(n);  
    REP(i, n) cin >> p[i].second;  
    REP(i, n) cin >> p[i].first;  
    sort(ALL(p));      
  
    map<PII,ll> pos;  
    vector<ll> a(n), b(n);  
    REP(i, n) {  
        a[i] = p[i].second;  
        b[i] = p[i].first;  
        pos[PII(a[i],i)] = i;  
    }  
  
    multiset<PII> st;  
    REP(i, n) st.insert(PII(a[i], i));  
  
    segtree<min_monoid<PII>> seg(n);  
    vector<PII> init(n);  
    REP(i, n) init[i] = PII(a[i], i);  
    seg.build(init);  
      
    ll cnt = 0;  
    while(st.size()) {  
        ll idx1 = st.rbegin()->second;  
        ll val1 = seg.query(idx1, idx1+1).first;  
        if(seg.query(idx1, idx1+1).first <= b[idx1]) {  
            st.erase(st.find(PII(val1, idx1)));  
            continue;  
        }  
  
        cnt++;  
        ll x = lower_bound(ALL(b), val1) - b.begin();  
        if(x == n) {  
            cout << "No" << endl;  
            return 0;  
        }  
        PII ret = seg.query(x, n);  
  
        ll idx2 = ret.second;  
        ll val2 = ret.first;  
  
        dump(idx1, val1, idx2, val2);  
        seg.update(idx1, PII(val2, idx1));  
        seg.update(idx2, PII(val1, idx2));  
          
        st.erase(st.find(PII(val1, idx1)));  
        st.erase(st.find(PII(val2, idx2)));  
        st.insert(PII(val2, idx1));  
    }  
  
    bool flag = true;  
    REP(i, n) if(seg.query(i, i+1).first > b[i]) flag = false;  
    if(cnt > n-2) flag = false;  
  
    if(flag) cout << "Yes" << endl;  
    else cout << "No" << endl;  
  
    return 0;  
}

ferinの競プロ帳

競プロについてのメモ

第二回全国統一プログラミング王決定戦予選 C - Swaps