verify/misc/mo.test.cpp

• View this file on GitHub
• Last update: 2026-04-11 00:41:57+09:00
• Problem: https://judge.yosupo.jp/problem/static_range_inversions_query

Depends on

• algebra/monoid/monoid_plus.hpp
• Mo's Algorithm (misc/mo.hpp)
• segment_tree/fenwick_tree.hpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/static_range_inversions_query"

#include <iostream>

#include "../../algebra/monoid/monoid_plus.hpp"
#include "../../misc/mo.hpp"
#include "../../segment_tree/fenwick_tree.hpp"

int main() {
    int N, Q;
    std::cin >> N >> Q;
    std::vector<int> A(N);
    for (int i = 0; i < N; i++) std::cin >> A[i];
    std::vector<int> L(Q), R(Q);
    for (int i = 0; i < Q; i++) std::cin >> L[i] >> R[i];

    auto B = A;
    std::sort(B.begin(), B.end());
    B.erase(std::unique(B.begin(), B.end()), B.end());
    for (auto&& e : A) e = std::lower_bound(B.begin(), B.end(), e) - B.begin();

    const int M = (int)(B.size());
    FenwickTree<MonoidPlus<long long>> fen(M);
    std::vector<long long> ans(Q);
    long long cur = 0;
    auto add_left = [&](int i) {
        cur += fen.prod(0, A[i]);
        fen.add(A[i], 1);
    };
    auto add_right = [&](int i) {
        cur += fen.prod(A[i] + 1, M);
        fen.add(A[i], 1);
    };
    auto del_left = [&](int i) {
        cur -= fen.prod(0, A[i]);
        fen.add(A[i], -1);
    };
    auto del_right = [&](int i) {
        cur -= fen.prod(A[i] + 1, M);
        fen.add(A[i], -1);
    };
    auto out = [&](int i) { ans[i] = cur; };
    mo(N, L, R, add_left, add_right, del_left, del_right, out);
    for (int i = 0; i < Q; i++) std::cout << ans[i] << '\n';
    return 0;
}

#line 1 "verify/misc/mo.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/static_range_inversions_query"

#include <iostream>

#line 2 "algebra/monoid/monoid_plus.hpp"

template <class T> struct MonoidPlus {
    using value_type = T;
    static constexpr T operation(const T& a, const T& b) noexcept {
        return a + b;
    }
    static constexpr T identity() noexcept { return T(0); }
    static constexpr T inverse(const T& a) noexcept { return -a; }
    static constexpr bool commutative = true;
};
#line 2 "misc/mo.hpp"

#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>

// Mo's Algorithm
// https://snuke.hatenablog.com/entry/2016/07/01/000000
// complexity: O(N * N / B + Q * B)
// -> O(N sqrt(Q)) (B := N / sqrt(Q))
template <class AddLeft, class AddRight, class DelLeft, class DelRight, class Out>
void mo(const int n, const std::vector<int> l, const std::vector<int> r, const AddLeft &add_left,
        const AddRight &add_right, const DelLeft &del_left, const DelRight &del_right,
        const Out &out, const int bucket_size_value = -1) {
    const int q = (int)(l.size());
    if (q == 0) return;
    // determine bucket size
    auto calculate_bucket_size = [&]() {
        // const int bucket_size = std::max(1.0, n / std::max(1.0, sqrt(q)));
        // speed up by https://nyaannyaan.github.io/library/misc/mo.hpp
        const int bucket_size = std::max(1.0, n / std::max(1.0, sqrt(2.0 * q / 3.0)));
        return bucket_size;
    };
    const int bucket_size = bucket_size_value == -1 ? calculate_bucket_size() : bucket_size_value;
    std::vector<int> ind(q), lbs(q);
    // reduce the number of divisions by memoization
    for (int i = 0; i < q; i++) lbs[i] = l[i] / bucket_size;
    std::iota(ind.begin(), ind.end(), 0);
    std::sort(ind.begin(), ind.end(), [&](int i, int j) {
        if (lbs[i] != lbs[j]) return l[i] < l[j];
        return (lbs[i] & 1) ? r[i] > r[j] : r[i] < r[j];
    });
    // 以前は now_l = now_r = l[ind.front()] としていたが, これは [now_l, now_r) に対する答えが
    // [0, 0) と同じでないと壊れる
    int now_l = 0, now_r = 0;
    for (auto &&i : ind) {
        while (now_l > l[i]) add_left(--now_l);
        while (now_r < r[i]) add_right(now_r++);
        while (now_l < l[i]) del_left(now_l++);
        while (now_r > r[i]) del_right(--now_r);
        out(i);
    }
}
template <class Add, class Del, class Out>                                  //
void mo(const int n, const std::vector<int> &l, const std::vector<int> &r,  //
        const Add &add, const Del &del, const Out &out, const int bucket_size_value = -1) {
    mo(n, l, r, add, add, del, del, out, bucket_size_value);
}
#line 2 "segment_tree/fenwick_tree.hpp"

#include <cassert>
#line 5 "segment_tree/fenwick_tree.hpp"

// Fenwick Tree
template <class MS> struct FenwickTree {
  public:
    using S = typename MS::value_type;

    FenwickTree() = default;

    explicit FenwickTree(int n)
        : FenwickTree(std::vector<S>(n, MS::identity())) {}

    explicit FenwickTree(const std::vector<S>& v) : n((int)(v.size())) {
        d = std::vector<S>(n + 1, MS::identity());
        for (int i = 1; i <= n; i++) {
            d[i] = MS::operation(d[i], v[i - 1]);
            int j = i + (i & -i);
            if (j <= n) {
                d[j] = MS::operation(d[j], d[i]);
            }
        }
    }

    void set(int p, const S& x) {
        assert(0 <= p and p < n);
        add(p, MS::operation(MS::inverse(get(p)), x));
    }
    void add(int p, const S& x) {
        assert(0 <= p and p < n);
        p++;  // 1-indexed
        while (p <= n) {
            d[p] = MS::operation(d[p], x);
            p += p & -p;
        }
    }

    S operator[](int p) const {
        assert(0 <= p and p < n);
        return prod(p, p + 1);
    }

    S get(int p) const {
        assert(0 <= p and p < n);
        return prod(p, p + 1);
    }

    S prod(int l, int r) const {
        assert(0 <= l and l <= r and r <= n);
        return MS::operation(prod(r), MS::inverse(prod(l)));
    }

    S prod(int p) const {
        assert(0 <= p and p <= n);
        S s = MS::identity();
        while (p > 0) {
            s = MS::operation(s, d[p]);
            p -= p & -p;
        }
        return s;
    }

    S all_prod() const { return prod(n); }

    std::vector<S> make_vector() {
        std::vector<S> vec(n);
        for (int i = 0; i < n; i++) vec[i] = get(i);
        return vec;
    }

  private:
    int n;
    std::vector<S> d;
};
#line 8 "verify/misc/mo.test.cpp"

int main() {
    int N, Q;
    std::cin >> N >> Q;
    std::vector<int> A(N);
    for (int i = 0; i < N; i++) std::cin >> A[i];
    std::vector<int> L(Q), R(Q);
    for (int i = 0; i < Q; i++) std::cin >> L[i] >> R[i];

    auto B = A;
    std::sort(B.begin(), B.end());
    B.erase(std::unique(B.begin(), B.end()), B.end());
    for (auto&& e : A) e = std::lower_bound(B.begin(), B.end(), e) - B.begin();

    const int M = (int)(B.size());
    FenwickTree<MonoidPlus<long long>> fen(M);
    std::vector<long long> ans(Q);
    long long cur = 0;
    auto add_left = [&](int i) {
        cur += fen.prod(0, A[i]);
        fen.add(A[i], 1);
    };
    auto add_right = [&](int i) {
        cur += fen.prod(A[i] + 1, M);
        fen.add(A[i], 1);
    };
    auto del_left = [&](int i) {
        cur -= fen.prod(0, A[i]);
        fen.add(A[i], -1);
    };
    auto del_right = [&](int i) {
        cur -= fen.prod(A[i] + 1, M);
        fen.add(A[i], -1);
    };
    auto out = [&](int i) { ans[i] = cur; };
    mo(N, L, R, add_left, add_right, del_left, del_right, out);
    for (int i = 0; i < Q; i++) std::cout << ans[i] << '\n';
    return 0;
}

Back to top page