test/yosupo/static-range-inversions-query.test.cpp

• View this file on GitHub
• Last update: 2026-10-12 20:24:58+09:00
• Problem: https://judge.yosupo.jp/problem/static_range_inversions_query

Depends on

• Mo's algorithm (src/others/mo.hpp)

Code

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

#include <algorithm>
#include <iostream>
#include <vector>

#include "../../src/others/mo.hpp"

int main() {
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    int n, q; std::cin >> n >> q;
    std::vector<int> a(n);
    for (int& x : a) std::cin >> x;
    // 座標圧縮
    std::vector<int> xs = a;
    std::sort(xs.begin(), xs.end());
    xs.erase(std::unique(xs.begin(), xs.end()), xs.end());
    for (int& x : a) x = std::lower_bound(xs.begin(), xs.end(), x) - xs.begin();
    int m = xs.size();

    // 区間内の値の個数を持つ Fenwick Tree
    std::vector<int> bit(m + 1);
    int total = 0;
    auto add = [&](int i, int v) {
        total += v;
        for (i++; i <= m; i += i & -i) bit[i] += v;
    };
    auto count_less = [&](int i) {
        int ret = 0;
        for (; i > 0; i -= i & -i) ret += bit[i];
        return ret;
    };
    auto count_greater = [&](int i) { return total - count_less(i + 1); };

    Mo mo(n, 0LL,
        [&](long long& inv, int i) { inv += count_less(a[i]); add(a[i], 1); },
        [&](long long& inv, int i) { add(a[i], -1); inv -= count_less(a[i]); },
        [&](long long& inv, int i) { inv += count_greater(a[i]); add(a[i], 1); },
        [&](long long& inv, int i) { add(a[i], -1); inv -= count_greater(a[i]); });
    for (int i = 0; i < q; i++) {
        int l, r; std::cin >> l >> r;
        mo.query(l, r);
    }
    for (long long ans : mo.solve<long long>([](long long& inv) { return inv; })) {
        std::cout << ans << '\n';
    }
}

#line 1 "test/yosupo/static-range-inversions-query.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/static_range_inversions_query"

#include <algorithm>
#include <iostream>
#include <vector>

#line 2 "src/others/mo.hpp"

/**
 * @file mo.hpp
 * @brief Mo's algorithm
 */

#line 9 "src/others/mo.hpp"
#include <array>
#include <type_traits>
#line 12 "src/others/mo.hpp"
#include <cmath>

template <typename U, class ADD_LEFT, class DELETE_LEFT, class ADD_RIGHT = ADD_LEFT, class DELETE_RIGHT = DELETE_LEFT>
struct Mo {
   private:
    int _n;
    std::vector<std::array<int, 3>> lri;
    U _e;
    ADD_LEFT _add_left;
    DELETE_LEFT _delete_left;
    ADD_RIGHT _add_right;
    DELETE_RIGHT _delete_right;

    static_assert(std::is_invocable_r_v<void, ADD_LEFT, U&, int>, "ADD_LEFT must be callable with (U&, int)");
    static_assert(std::is_invocable_r_v<void, DELETE_LEFT, U&, int>, "DELETE_LEFT must be callable with (U&, int)");
    static_assert(std::is_invocable_r_v<void, ADD_RIGHT, U&, int>, "ADD_RIGHT must be callable with (U&, int)");
    static_assert(std::is_invocable_r_v<void, DELETE_RIGHT, U&, int>, "DELETE_RIGHT must be callable with (U&, int)");

   public:
    Mo(int n,
       const U& e,
       const ADD_LEFT& add_left,
       const DELETE_LEFT& delete_left,
       const ADD_RIGHT& add_right,
       const DELETE_RIGHT& delete_right) : _n(n), lri(), _e(e), _add_left(add_left), _delete_left(delete_left), _add_right(add_right), _delete_right(delete_right) {}
    Mo(int n,
       const U& e,
       const ADD_LEFT& add_left,
       const DELETE_LEFT& delete_left) : _n(n), lri(), _e(e), _add_left(add_left), _delete_left(delete_left), _add_right(add_left), _delete_right(delete_left) {}
    void query(int l, int r) {
        lri.push_back({l, r, (int)lri.size()});
    }
    template <typename T, class F>
    std::vector<T> solve(const F& f) {
        static_assert(std::is_invocable_r_v<T, F, U&>, "The function passed to solve must be callable with (U&) and return T");
        
        const int w = std::max<int>(1, 1.0 * _n / std::max<double>(1.0, std::sqrt(lri.size() * 2.0 / 3.0)));
        std::sort(lri.begin(), lri.end(), [=](const std::array<int, 3>& a, const std::array<int, 3>& b) {
            int aw = a[0] / w;
            int bw = b[0] / w;
            if (aw != bw) return aw < bw;
            if (aw & 1) return a[1] > b[1];
            return a[1] < b[1];
        });
        std::vector<T> res(lri.size());
        long long tmpl = 0, tmpr = 0;
        U tmp = _e;
        for (auto [l, r, i] : lri) {
            while (tmpl > l) {
                tmpl--;
                _add_left(tmp, tmpl);
            }
            while (tmpr < r) {
                _add_right(tmp, tmpr);
                tmpr++;
            }
            while (tmpl < l) {
                _delete_left(tmp, tmpl);
                tmpl++;
            }
            while (tmpr > r) {
                tmpr--;
                _delete_right(tmp, tmpr);
            }
            res[i] = f(tmp);
        }
        return res;
    }
};
#line 8 "test/yosupo/static-range-inversions-query.test.cpp"

int main() {
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    int n, q; std::cin >> n >> q;
    std::vector<int> a(n);
    for (int& x : a) std::cin >> x;
    // 座標圧縮
    std::vector<int> xs = a;
    std::sort(xs.begin(), xs.end());
    xs.erase(std::unique(xs.begin(), xs.end()), xs.end());
    for (int& x : a) x = std::lower_bound(xs.begin(), xs.end(), x) - xs.begin();
    int m = xs.size();

    // 区間内の値の個数を持つ Fenwick Tree
    std::vector<int> bit(m + 1);
    int total = 0;
    auto add = [&](int i, int v) {
        total += v;
        for (i++; i <= m; i += i & -i) bit[i] += v;
    };
    auto count_less = [&](int i) {
        int ret = 0;
        for (; i > 0; i -= i & -i) ret += bit[i];
        return ret;
    };
    auto count_greater = [&](int i) { return total - count_less(i + 1); };

    Mo mo(n, 0LL,
        [&](long long& inv, int i) { inv += count_less(a[i]); add(a[i], 1); },
        [&](long long& inv, int i) { add(a[i], -1); inv -= count_less(a[i]); },
        [&](long long& inv, int i) { inv += count_greater(a[i]); add(a[i], 1); },
        [&](long long& inv, int i) { add(a[i], -1); inv -= count_greater(a[i]); });
    for (int i = 0; i < q; i++) {
        int l, r; std::cin >> l >> r;
        mo.query(l, r);
    }
    for (long long ans : mo.solve<long long>([](long long& inv) { return inv; })) {
        std::cout << ans << '\n';
    }
}

Back to top page