1513F - Swapping Problem - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;

const int INF = 2e9 + 5;

class segtree {
  private:
    struct node {
        int mx;
        int mx_index;
        
        node() : mx(-INF) { }
        
        node(int i) : mx(-INF), mx_index(i) { }

        void assign(int v) {
            mx = v;
        }

        void merge(const node &a, const node &b) {
            if (a.mx > b.mx) {
                mx = a.mx;
                mx_index = a.mx_index;
            } else {
                mx = b.mx;
                mx_index = b.mx_index;
            }
        }
    };

    int b;
    vector<node> tree;

  public:
    const int n;
    
    segtree(int _n) : n(_n) {
        assert(_n > 0);
        for (b = 1; b < n; b <<= 1);
        tree.resize(b << 1);
        for (int i = 0; i < n; i++) {
            tree[b + i] = node(i);
        }
        for (int i = b - 1; i > 0; i--) {
            tree[i].merge(tree[i * 2], tree[i * 2 + 1]);
        }
    }
    
    template <typename... M>
    void update(int ind, const M&... v) {
        assert(0 <= ind && ind < n);
        tree[b + ind].assign(v...);
        for (int i = (b + ind) / 2; i > 0; i >>= 1) {
            tree[i].merge(tree[i * 2], tree[i * 2 + 1]);
        }
    }

    node get(int l, int r) const {
        assert(0 <= l && l <= r && r < n);
        l += b;
        r += b;
        if (l == r) return tree[l];
        node left = tree[l];
        node right = tree[r];
        while (l + 1 < r) {
            if (l % 2 == 0) left.merge(left, tree[l + 1]);
            if (r % 2) right.merge(tree[r - 1], right);
            l /= 2;
            r /= 2;
        }
        node answer;
        answer.merge(left, right);
        return answer;
    }
};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    vector<pair<int,int>> as(n), bs(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        as[i] = make_pair(a[i], i);
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
        bs[i] = make_pair(b[i], i);
    }
    sort(as.begin(), as.end());
    sort(bs.begin(), bs.end());
    long long value = 0;
    for (int i = 0; i < n; i++) {
        value += abs(a[i] - b[i]);
    }
    long long ans = value;
    auto check = [&](int i, int j) {
        long long nval = value;
        nval -= abs(a[i] - b[i]);
        nval -= abs(a[j] - b[j]);
        nval += abs(a[i] - b[j]);
        nval += abs(a[j] - b[i]);
        ans = min(ans, nval);
    };
    int mx_b = -1;
    int mx_b_val = -1;
    int ptr = 0;
    for (const auto &[bi, i] : bs) {
        while (ptr < n && as[ptr].first <= b[i]) {
            int j = as[ptr++].second;
            if (b[j] > mx_b_val) {
                mx_b_val = b[j];
                mx_b = j;
            }
        }
        if (mx_b != -1) {
            check(i, mx_b);
        }
    }
    ptr = n - 1;
    segtree st1(n), st2(n);
    for (int ind = n - 1; ind >= 0; ind--) {
        const int i = bs[ind].second;
        while (ptr >= 0 && as[ptr].first >= b[i]) {
            int j = as[ptr--].second;
            int pos = lower_bound(bs.begin(), bs.end(), make_pair(b[j], j)) - bs.begin();
            st1.update(pos, -a[j]);
            st2.update(pos, b[j] - a[j]);
        }
        int pos = lower_bound(bs.begin(), bs.end(), make_pair(a[i], -1)) - bs.begin();
        if (pos > 0) {
            int mxi = st1.get(0, pos - 1).mx_index;
            int j = bs[mxi].second;
            assert(b[j] < a[i]);
            check(i, j);
        }
        pos = lower_bound(bs.begin(), bs.end(), make_pair(a[i], -1)) - bs.begin();
        if (pos < n) {
            int mxi = st2.get(pos, n - 1).mx_index;
            int j = bs[mxi].second;
            assert(b[j] >= a[i]);
            check(i, j);
        }
    }
    cout << ans << '\n';
}