utils/mo_algorithm.yuki1270.test.cpp

View this file on GitHub
Last update: 2021-08-30 04:35:37+09:00
Problem: https://yukicoder.me/problems/no/1270

Depends on

Code

#define PROBLEM "https://yukicoder.me/problems/no/1270"
#include <algorithm>
#include <cassert>
#include <iostream>
#include <unordered_map>
#include <utility>
#include <vector>
#include "../utils/macros.hpp"
#include "../data_structure/segment_tree.hpp"
#include "../data_structure/lazy_propagation_segment_tree.hpp"
#include "../monoids/min.hpp"
#include "../monoids/plus.hpp"
#include "../monoids/plus_min_action.hpp"
#include "../utils/mo_algorithm.hpp"
using namespace std;


struct mo_struct {
    typedef int64_t value_type;
    typedef int64_t result_type;

private:
    typedef segment_tree<plus_monoid<int> > plus_segtree_type;
    typedef lazy_propagation_segment_tree<min_monoid<int64_t>, plus_monoid<int64_t>, plus_min_action<int64_t> > plus_min_segtree_type;

    // input
    int n;
    const vector<int64_t>& a;

    // static
    unordered_map<int64_t, int> compress;
    int k;
    vector<int64_t> dp_l;
    vector<int64_t> dp_r;

    // dynamic
    int l;
    int r;
    int64_t value_lr;
    plus_segtree_type segtree_l;
    plus_min_segtree_type segtree_m;
    plus_segtree_type segtree_r;

public:
    mo_struct(const vector<int64_t>& a_)
            : n(a_.size())
            , a(a_) {
        // static compress
        vector<int64_t> sorted_a = a;
        sort(ALL(sorted_a));
        for (int64_t a_i : sorted_a) {
            compress.emplace(a_i, compress.size());
        }
        k = compress.size();

        // static left
        dp_l.resize(n + 1);
        segtree_l = plus_segtree_type(k);
        segtree_l.range_set(0, k, 0);
        REP (i, n) {
            dp_l[i + 1] = dp_l[i] + segtree_l.range_get(compress[a[i]] + 1, k);
            segtree_l.point_set(compress[a[i]], segtree_l.point_get(compress[a[i]]) + 1);
        }
        segtree_l = plus_segtree_type(k);
        segtree_l.range_set(0, k, 0);

        // static right
        dp_r.resize(n + 1);
        segtree_r = plus_segtree_type(k);
        segtree_r.range_set(0, k, 0);
        REP_R (i, n) {
            dp_r[i] = dp_r[i + 1] + segtree_r.range_get(0, compress[a[i]]);
            segtree_r.point_set(compress[a[i]], segtree_r.point_get(compress[a[i]]) + 1);
        }

        // dynamic
        l = 0;
        r = 0;
        value_lr = 0;
        segtree_m = plus_min_segtree_type(k);
        segtree_m.range_set(0, k, 0);
        REP (i, n) {
            segtree_m.range_apply(compress[a[i]] + 1, k, 1);
        }
    }

    void add_right(int nr, int64_t x_r) {
        assert (nr == r + 1);
        int y = compress[x_r];
        value_lr -= segtree_l.range_get(y + 1, k);
        segtree_m.range_apply(y + 1, k, -1);
        segtree_r.point_set(y, segtree_r.point_get(y) - 1);
        r = nr;
    }

    void add_left(int nl, int64_t x_nl) {
        assert (nl == l - 1);
        int y = compress[x_nl];
        value_lr -= segtree_r.range_get(0, y);
        segtree_l.point_set(y, segtree_l.point_get(y) - 1);
        segtree_m.range_apply(0, y, -1);
        l = nl;
    }

    void remove_right(int nr, int64_t x_nr) {
        assert (nr == r - 1);
        int y = compress[x_nr];
        value_lr += segtree_l.range_get(y + 1, k);
        segtree_m.range_apply(y + 1, k, 1);
        segtree_r.point_set(y, segtree_r.point_get(y) + 1);
        r = nr;
    }

    void remove_left(int nl, int64_t x_l) {
        assert (nl == l + 1);
        int y = compress[x_l];
        value_lr += segtree_r.range_get(0, y);
        segtree_l.point_set(y, segtree_l.point_get(y) + 1);
        segtree_m.range_apply(0, y, 1);
        l = nl;
    }

    int64_t query() {
        int64_t ans = 0;
        ans += dp_l[l];  // the inversion number in [0, l)
        ans += dp_r[r];  // the inversion number in [r, n)
        ans += value_lr;  // the inversion number between [0, l) and [r, n)
        ans += (int64_t)(r - l) * segtree_m.range_get(0, k);  // the inversion number between [0, l) and [l, r) plus the inversion number between [l, r) and [r, n)
        return ans;
    }
};

vector<int64_t> solve(int n, int q, const vector<int64_t>& a, const vector<pair<int, int> >& queries) {
    return run_mo_algorithm(mo_struct(a), a, queries);
}

int main() {
    int n, q; cin >> n >> q;
    vector<int64_t> a(n);
    REP (i, n) {
        cin >> a[i];
    }
    vector<pair<int, int> > queries(q);
    REP (i, q) {
        int l, r; cin >> l >> r;
        -- l;
        queries[i] = make_pair(l, r);
    }
    auto ans = solve(n, q, a, queries);
    REP (i, q) {
        cout << ans[i] << endl;
    }
    return 0;
}

#line 1 "utils/mo_algorithm.yuki1270.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/1270"
#include <algorithm>
#include <cassert>
#include <iostream>
#include <unordered_map>
#include <utility>
#include <vector>
#line 2 "utils/macros.hpp"
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
#define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))
#define ALL(x) std::begin(x), std::end(x)
#line 6 "data_structure/segment_tree.hpp"

/**
 * @brief Segment Tree / セグメント木 (monoids, 完全二分木)
 * @docs data_structure/segment_tree.md
 * @tparam Monoid (commutativity is not required)
 */
template <class Monoid>
struct segment_tree {
    typedef typename Monoid::value_type value_type;
    Monoid mon;
    int n;
    std::vector<value_type> a;
    segment_tree() = default;
    segment_tree(int n_, const Monoid & mon_ = Monoid()) : mon(mon_) {
        n = 1; while (n < n_) n *= 2;
        a.resize(2 * n - 1, mon.unit());
    }
    void point_set(int i, value_type b) {  // 0-based
        assert (0 <= i and i < n);
        a[i + n - 1] = b;
        for (i = (i + n) / 2; i > 0; i /= 2) {  // 1-based
            a[i - 1] = mon.mult(a[2 * i - 1], a[2 * i]);
        }
    }
    value_type range_get(int l, int r) {  // 0-based, [l, r)
        assert (0 <= l and l <= r and r <= n);
        value_type lacc = mon.unit(), racc = mon.unit();
        for (l += n, r += n; l < r; l /= 2, r /= 2) {  // 1-based loop, 2x faster than recursion
            if (l % 2 == 1) lacc = mon.mult(lacc, a[(l ++) - 1]);
            if (r % 2 == 1) racc = mon.mult(a[(-- r) - 1], racc);
        }
        return mon.mult(lacc, racc);
    }

    value_type point_get(int i) {  // 0-based
        assert (0 <= i and i < n);
        return a[i + n - 1];
    }

    /**
     * @note O(min(n, (r - l) log n))
     */
    void range_set(int l, int r, value_type b) {
        assert (0 <= l and l <= r and r <= n);
        range_set(0, 0, n, l, r, b);
    }
    void range_set(int i, int il, int ir, int l, int r, value_type b) {
        if (l <= il and ir <= r and ir - il == 1) {  // 0-based
            a[i] = b;
        } else if (ir <= l or r <= il) {
            // nop
        } else {
            range_set(2 * i + 1, il, (il + ir) / 2, l, r, b);
            range_set(2 * i + 2, (il + ir) / 2, ir, l, r, b);
            a[i] = mon.mult(a[2 * i + 1], a[2 * i + 2]);
        }
    }

    /**
     * @brief a fast & semigroup-friendly version constructor
     * @note $O(n)$
     */
    template <class InputIterator>
    segment_tree(InputIterator first, InputIterator last, const Monoid & mon_ = Monoid()) : mon(mon_) {
        int size = std::distance(first, last);
        n = 1; while (n < size) n *= 2;
        a.resize(2 * n - 1, mon.unit());
        std::copy(first, last, a.begin() + (n - 1));
        unsafe_rebuild();
    }
    /**
     * @brief update a leaf node without updating ancestors
     * @note $O(1)$
     */
    void unsafe_point_set(int i, value_type b) {  // 0-based
        assert (0 <= i and i < n);
        a[i + n - 1] = b;
    }
    /**
     * @brief re-build non-leaf nodes from leaf nodes
     * @note $O(n)$
     */
    void unsafe_rebuild() {
        REP_R (i, n - 1) {
            a[i] = mon.mult(a[2 * i + 1], a[2 * i + 2]);
        }
    }
};
#line 4 "data_structure/lazy_propagation_segment_tree.hpp"
#include <type_traits>
#line 7 "data_structure/lazy_propagation_segment_tree.hpp"

/**
 * @brief Lazy Propagation Segment Tree / 遅延伝播セグメント木 (monoids, 完全二分木)
 * @docs data_structure/lazy_propagation_segment_tree.md
 * @tparam MonoidX is a monoid
 * @tparam MonoidF is a monoid
 * @tparam Action is a function phi : F * X -> X where the partial applied phi(f, -) : X -> X is a homomorphism on X
 */
template <class MonoidX, class MonoidF, class Action>
struct lazy_propagation_segment_tree {
    static_assert (std::is_invocable_r<typename MonoidX::value_type, Action, typename MonoidF::value_type, typename MonoidX::value_type>::value, "");
    typedef typename MonoidX::value_type value_type;
    typedef typename MonoidF::value_type operator_type;
    MonoidX mon_x;
    MonoidF mon_f;
    Action act;
    int n;
    std::vector<value_type> a;
    std::vector<operator_type> f;

    lazy_propagation_segment_tree() = default;
    lazy_propagation_segment_tree(int n_, const MonoidX & mon_x_ = MonoidX(), const MonoidF & mon_f_ = MonoidF(), const Action & act_ = Action())
            : mon_x(mon_x_), mon_f(mon_f_), act(act_) {
        n = 1; while (n < n_) n *= 2;
        a.resize(2 * n - 1, mon_x.unit());
        f.resize(n - 1, mon_f.unit());
    }
    template <class InputIterator>
    lazy_propagation_segment_tree(InputIterator first, InputIterator last, const MonoidX & mon_x_ = MonoidX(), const MonoidF & mon_f_ = MonoidF(), const Action & act_ = Action())
            : mon_x(mon_x_), mon_f(mon_f_), act(act_) {
        int size = std::distance(first, last);
        n = 1; while (n < size) n *= 2;
        a.resize(2 * n - 1, mon_x.unit());
        f.resize(n - 1, mon_f.unit());
        std::copy(first, last, a.begin() + (n - 1));
        REP_R (i, n - 1) {
            a[i] = mon_x.mult(a[2 * i + 1], a[2 * i + 2]);
        }
    }

    void point_set(int i, value_type b) {
        range_set(i, i + 1, b);
    }
    /**
     * @note O(min(n, (r - l) log n))
     */
    void range_set(int l, int r, value_type b) {
        assert (0 <= l and l <= r and r <= n);
        range_set(0, 0, n, l, r, b);
    }
    void range_set(int i, int il, int ir, int l, int r, value_type b) {
        if (l <= il and ir <= r and ir - il == 1) {  // 0-based
            a[i] = b;
        } else if (ir <= l or r <= il) {
            // nop
        } else {
            range_apply(2 * i + 1, il, (il + ir) / 2, 0, n, f[i]);
            range_apply(2 * i + 2, (il + ir) / 2, ir, 0, n, f[i]);
            f[i] = mon_f.unit();
            range_set(2 * i + 1, il, (il + ir) / 2, l, r, b);
            range_set(2 * i + 2, (il + ir) / 2, ir, l, r, b);
            a[i] = mon_x.mult(a[2 * i + 1], a[2 * i + 2]);
        }
    }

    void point_apply(int i, operator_type g) {
        range_apply(i, i + 1, g);
    }
    void range_apply(int l, int r, operator_type g) {
        assert (0 <= l and l <= r and r <= n);
        range_apply(0, 0, n, l, r, g);
    }
    void range_apply(int i, int il, int ir, int l, int r, operator_type g) {
        if (l <= il and ir <= r) { // 0-based
            a[i] = act(g, a[i]);
            if (i < f.size()) f[i] = mon_f.mult(g, f[i]);
        } else if (ir <= l or r <= il) {
            // nop
        } else {
            range_apply(2 * i + 1, il, (il + ir) / 2, 0, n, f[i]);
            range_apply(2 * i + 2, (il + ir) / 2, ir, 0, n, f[i]);
            f[i] = mon_f.unit();  // unnecessary if the oprator monoid is commutative
            range_apply(2 * i + 1, il, (il + ir) / 2, l, r, g);
            range_apply(2 * i + 2, (il + ir) / 2, ir, l, r, g);
            a[i] = mon_x.mult(a[2 * i + 1], a[2 * i + 2]);
        }
    }

    value_type point_get(int i) {
        return range_get(i, i + 1);
    }
    value_type range_get(int l, int r) {
        assert (0 <= l and l <= r and r <= n);
        if (l == 0 and r == n) return a[0];
        value_type lacc = mon_x.unit(), racc = mon_x.unit();
        for (int l1 = (l += n), r1 = (r += n) - 1; l1 > 1; l /= 2, r /= 2, l1 /= 2, r1 /= 2) {  // 1-based loop, 2x faster than recursion
            if (l < r) {
                if (l % 2 == 1) lacc = mon_x.mult(lacc, a[(l ++) - 1]);
                if (r % 2 == 1) racc = mon_x.mult(a[(-- r) - 1], racc);
            }
            lacc = act(f[l1 / 2 - 1], lacc);
            racc = act(f[r1 / 2 - 1], racc);
        }
        return mon_x.mult(lacc, racc);
    }
};
#line 3 "monoids/min.hpp"
#include <limits>

template <class T>
struct min_monoid {
    typedef T value_type;
    value_type unit() const { return std::numeric_limits<T>::max(); }
    value_type mult(value_type a, value_type b) const { return std::min(a, b); }
};
#line 2 "monoids/plus.hpp"

template <class T>
struct plus_monoid {
    typedef T value_type;
    value_type unit() const { return value_type(); }
    value_type mult(value_type a, value_type b) const { return a + b; }
};
#line 4 "monoids/plus_min_action.hpp"

template <class T>
struct plus_min_action {
    typename min_monoid<T>::value_type operator () (typename plus_monoid<T>::value_type f, typename min_monoid<T>::value_type x) const {
        return (x == min_monoid<T>().unit() ? x : f + x);
    }
};
#line 3 "utils/mo_algorithm.hpp"
#include <cmath>
#include <numeric>
#include <tuple>
#line 8 "utils/mo_algorithm.hpp"

// struct mo_struct {
//     typedef int64_t value_type;
//     typedef int64_t result_type;
//     void add_right(int nr, value_type x_r) {
//     }
//     void add_left(int nl, value_type x_nl) {
//     }
//     void remove_right(int nr, value_type x_nr) {
//     }
//     void remove_left(int nl, value_type x_l) {
//     }
//     result_type query() {
//         return 0;
//     }
// };

template <class Mo>
std::vector<typename Mo::result_type> run_mo_algorithm(Mo mo, const std::vector<typename Mo::value_type>& values, const std::vector<std::pair<int, int> >& queries) {
    int n = values.size();
    int m = queries.size();

    // sort queries
    int sq_n = std::sqrt(n);
    std::vector<int> order(m);
    std::iota(ALL(order), 0);
    std::sort(ALL(order), [&](int i, int j) {
        int l_i, r_i; std::tie(l_i, r_i) = queries[i];
        int l_j, r_j; std::tie(l_j, r_j) = queries[j];
        return std::make_pair(l_i / sq_n, r_i) < std::make_pair(l_j / sq_n, r_j);
    });

    // compute queries
    std::vector<typename Mo::result_type> ans(m);
    int l = 0;
    int r = 0;
    for (int j : order) {
        int nl, nr; std::tie(nl, nr) = queries[j];
        for (; r < nr; ++ r) mo.add_right(r + 1, values[r]);
        for (; nl < l; -- l) mo.add_left(l - 1, values[l - 1]);
        for (; nr < r; -- r) mo.remove_right(r - 1, values[r - 1]);
        for (; l < nl; ++ l) mo.remove_left(l + 1, values[l]);
        ans[j] = mo.query();
    }
    return ans;
}
#line 15 "utils/mo_algorithm.yuki1270.test.cpp"
using namespace std;


struct mo_struct {
    typedef int64_t value_type;
    typedef int64_t result_type;

private:
    typedef segment_tree<plus_monoid<int> > plus_segtree_type;
    typedef lazy_propagation_segment_tree<min_monoid<int64_t>, plus_monoid<int64_t>, plus_min_action<int64_t> > plus_min_segtree_type;

    // input
    int n;
    const vector<int64_t>& a;

    // static
    unordered_map<int64_t, int> compress;
    int k;
    vector<int64_t> dp_l;
    vector<int64_t> dp_r;

    // dynamic
    int l;
    int r;
    int64_t value_lr;
    plus_segtree_type segtree_l;
    plus_min_segtree_type segtree_m;
    plus_segtree_type segtree_r;

public:
    mo_struct(const vector<int64_t>& a_)
            : n(a_.size())
            , a(a_) {
        // static compress
        vector<int64_t> sorted_a = a;
        sort(ALL(sorted_a));
        for (int64_t a_i : sorted_a) {
            compress.emplace(a_i, compress.size());
        }
        k = compress.size();

        // static left
        dp_l.resize(n + 1);
        segtree_l = plus_segtree_type(k);
        segtree_l.range_set(0, k, 0);
        REP (i, n) {
            dp_l[i + 1] = dp_l[i] + segtree_l.range_get(compress[a[i]] + 1, k);
            segtree_l.point_set(compress[a[i]], segtree_l.point_get(compress[a[i]]) + 1);
        }
        segtree_l = plus_segtree_type(k);
        segtree_l.range_set(0, k, 0);

        // static right
        dp_r.resize(n + 1);
        segtree_r = plus_segtree_type(k);
        segtree_r.range_set(0, k, 0);
        REP_R (i, n) {
            dp_r[i] = dp_r[i + 1] + segtree_r.range_get(0, compress[a[i]]);
            segtree_r.point_set(compress[a[i]], segtree_r.point_get(compress[a[i]]) + 1);
        }

        // dynamic
        l = 0;
        r = 0;
        value_lr = 0;
        segtree_m = plus_min_segtree_type(k);
        segtree_m.range_set(0, k, 0);
        REP (i, n) {
            segtree_m.range_apply(compress[a[i]] + 1, k, 1);
        }
    }

    void add_right(int nr, int64_t x_r) {
        assert (nr == r + 1);
        int y = compress[x_r];
        value_lr -= segtree_l.range_get(y + 1, k);
        segtree_m.range_apply(y + 1, k, -1);
        segtree_r.point_set(y, segtree_r.point_get(y) - 1);
        r = nr;
    }

    void add_left(int nl, int64_t x_nl) {
        assert (nl == l - 1);
        int y = compress[x_nl];
        value_lr -= segtree_r.range_get(0, y);
        segtree_l.point_set(y, segtree_l.point_get(y) - 1);
        segtree_m.range_apply(0, y, -1);
        l = nl;
    }

    void remove_right(int nr, int64_t x_nr) {
        assert (nr == r - 1);
        int y = compress[x_nr];
        value_lr += segtree_l.range_get(y + 1, k);
        segtree_m.range_apply(y + 1, k, 1);
        segtree_r.point_set(y, segtree_r.point_get(y) + 1);
        r = nr;
    }

    void remove_left(int nl, int64_t x_l) {
        assert (nl == l + 1);
        int y = compress[x_l];
        value_lr += segtree_r.range_get(0, y);
        segtree_l.point_set(y, segtree_l.point_get(y) + 1);
        segtree_m.range_apply(0, y, 1);
        l = nl;
    }

    int64_t query() {
        int64_t ans = 0;
        ans += dp_l[l];  // the inversion number in [0, l)
        ans += dp_r[r];  // the inversion number in [r, n)
        ans += value_lr;  // the inversion number between [0, l) and [r, n)
        ans += (int64_t)(r - l) * segtree_m.range_get(0, k);  // the inversion number between [0, l) and [l, r) plus the inversion number between [l, r) and [r, n)
        return ans;
    }
};

vector<int64_t> solve(int n, int q, const vector<int64_t>& a, const vector<pair<int, int> >& queries) {
    return run_mo_algorithm(mo_struct(a), a, queries);
}

int main() {
    int n, q; cin >> n >> q;
    vector<int64_t> a(n);
    REP (i, n) {
        cin >> a[i];
    }
    vector<pair<int, int> > queries(q);
    REP (i, q) {
        int l, r; cin >> l >> r;
        -- l;
        queries[i] = make_pair(l, r);
    }
    auto ans = solve(n, q, a, queries);
    REP (i, q) {
        cout << ans[i] << endl;
    }
    return 0;
}