test/library-checker/static_range_inversions_query.test.cpp

• View this file on GitHub
• Last update: 2026-10-26 21:23:55+09:00
• Problem: https://judge.yosupo.jp/problem/static_range_inversions_query

Depends on

• Mo's Algorithm (algorithm/mo.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/static_range_inversions_query"
#include <algorithm>
#include <iostream>
#include <vector>

#include "algorithm/mo.hpp"
#include "atcoder/fenwicktree.hpp"

int main() {
    int n, q;
    std::cin >> n >> q;
    std::vector<int> a(n);
    for (auto& x : a) std::cin >> x;
    std::vector<int> v = a;
    std::sort(v.begin(), v.end());
    v.erase(std::unique(v.begin(), v.end()), v.end());
    for (auto& x : a) x = std::lower_bound(v.begin(), v.end(), x) - v.begin();
    int m = v.size();
    mo mo;
    for (int i = 0; i < q; i++) {
        int l, r;
        std::cin >> l >> r;
        mo.add(l, r);
    }
    atcoder::fenwick_tree<int> ft(m);
    long long inv = 0;
    int size = 0;
    std::vector<long long> ans(q);
    mo.run([&](int i) { inv += ft.sum(0, a[i]); ft.add(a[i], 1); size++; },
           [&](int i) { inv += size - ft.sum(0, a[i] + 1); ft.add(a[i], 1); size++; },
           [&](int i) { ft.add(a[i], -1); size--; inv -= ft.sum(0, a[i]); },
           [&](int i) { ft.add(a[i], -1); size--; inv -= size - ft.sum(0, a[i] + 1); },
           [&](int k) { ans[k] = inv; });
    for (auto x : ans) std::cout << x << '\n';
}

#line 1 "test/library-checker/static_range_inversions_query.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/static_range_inversions_query"
#include <algorithm>
#include <iostream>
#include <vector>

#line 3 "algorithm/mo.hpp"
#include <cassert>
#include <cmath>
#include <cstdlib>
#include <numeric>
#include <utility>
#line 9 "algorithm/mo.hpp"

struct mo {
    mo() = default;
    int add(int l, int r) {
        assert(0 <= l && l <= r);
        lr.emplace_back(l, r);
        return (int)lr.size() - 1;
    }
    void run(auto add_left, auto add_right, auto erase_left, auto erase_right,
             auto query) const {
        int l = 0, r = 0;
        for (int i : order()) {
            while (l > lr[i].first) add_left(--l);
            while (r < lr[i].second) add_right(r++);
            while (l < lr[i].first) erase_left(l++);
            while (r > lr[i].second) erase_right(--r);
            query(i);
        }
    }
    void run(auto add, auto erase, auto query) const {
        run(add, add, erase, erase, query);
    }

  private:
    std::vector<std::pair<int, int>> lr;
    std::vector<int> order() const {
        int q = lr.size();
        if (q == 0) return {};
        int n = 1;
        for (auto [l, r] : lr) n = std::max(n, r);
        int w = std::max(1, (int)(std::sqrt(3.0) * n / std::sqrt(2.0 * q)));
        std::vector<int> ord(q);
        std::iota(ord.begin(), ord.end(), 0);
        std::sort(ord.begin(), ord.end(), [&](int a, int b) {
            int ba = lr[a].first / w, bb = lr[b].first / w;
            if (ba != bb) return ba < bb;
            return (ba & 1) ? lr[a].second > lr[b].second
                            : lr[a].second < lr[b].second;
        });
        auto cost = [&](int a, int b) {
            return std::abs(lr[ord[a]].first - lr[ord[b]].first) +
                   std::abs(lr[ord[a]].second - lr[ord[b]].second);
        };
        auto improve = [&](int k) {
            if (cost(k, k + 2) + cost(k + 1, k + 3) <
                cost(k, k + 1) + cost(k + 2, k + 3))
                std::swap(ord[k + 1], ord[k + 2]);
            if (cost(k, k + 3) + cost(k + 1, k + 4) <
                cost(k, k + 1) + cost(k + 3, k + 4))
                std::swap(ord[k + 1], ord[k + 3]);
        };
        for (int k = 0; k + 5 <= q; k++) improve(k);
        for (int k = q - 5; k >= 0; k--) improve(k);
        return ord;
    }
};
#line 1 "atcoder/fenwicktree.hpp"



#line 6 "atcoder/fenwicktree.hpp"

#line 1 "atcoder/internal_type_traits.hpp"



#line 6 "atcoder/internal_type_traits.hpp"
#include <type_traits>

namespace atcoder {

namespace internal {

#ifndef _MSC_VER
template <class T>
using is_signed_int128 =
    typename std::conditional<std::is_same<T, __int128_t>::value ||
                                  std::is_same<T, __int128>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using is_unsigned_int128 =
    typename std::conditional<std::is_same<T, __uint128_t>::value ||
                                  std::is_same<T, unsigned __int128>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using make_unsigned_int128 =
    typename std::conditional<std::is_same<T, __int128_t>::value,
                              __uint128_t,
                              unsigned __int128>;

template <class T>
using is_integral = typename std::conditional<std::is_integral<T>::value ||
                                                  is_signed_int128<T>::value ||
                                                  is_unsigned_int128<T>::value,
                                              std::true_type,
                                              std::false_type>::type;

template <class T>
using is_signed_int = typename std::conditional<(is_integral<T>::value &&
                                                 std::is_signed<T>::value) ||
                                                    is_signed_int128<T>::value,
                                                std::true_type,
                                                std::false_type>::type;

template <class T>
using is_unsigned_int =
    typename std::conditional<(is_integral<T>::value &&
                               std::is_unsigned<T>::value) ||
                                  is_unsigned_int128<T>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using to_unsigned = typename std::conditional<
    is_signed_int128<T>::value,
    make_unsigned_int128<T>,
    typename std::conditional<std::is_signed<T>::value,
                              std::make_unsigned<T>,
                              std::common_type<T>>::type>::type;

#else

template <class T> using is_integral = typename std::is_integral<T>;

template <class T>
using is_signed_int =
    typename std::conditional<is_integral<T>::value && std::is_signed<T>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using is_unsigned_int =
    typename std::conditional<is_integral<T>::value &&
                                  std::is_unsigned<T>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using to_unsigned = typename std::conditional<is_signed_int<T>::value,
                                              std::make_unsigned<T>,
                                              std::common_type<T>>::type;

#endif

template <class T>
using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;

template <class T>
using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;

template <class T> using to_unsigned_t = typename to_unsigned<T>::type;

}  // namespace internal

}  // namespace atcoder


#line 8 "atcoder/fenwicktree.hpp"

namespace atcoder {

// Reference: https://en.wikipedia.org/wiki/Fenwick_tree
template <class T> struct fenwick_tree {
    using U = internal::to_unsigned_t<T>;

  public:
    fenwick_tree() : _n(0) {}
    explicit fenwick_tree(int n) : _n(n), data(n) {}

    void add(int p, T x) {
        assert(0 <= p && p < _n);
        p++;
        while (p <= _n) {
            data[p - 1] += U(x);
            p += p & -p;
        }
    }

    T sum(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        return sum(r) - sum(l);
    }

  private:
    int _n;
    std::vector<U> data;

    U sum(int r) {
        U s = 0;
        while (r > 0) {
            s += data[r - 1];
            r -= r & -r;
        }
        return s;
    }
};

}  // namespace atcoder


#line 8 "test/library-checker/static_range_inversions_query.test.cpp"

int main() {
    int n, q;
    std::cin >> n >> q;
    std::vector<int> a(n);
    for (auto& x : a) std::cin >> x;
    std::vector<int> v = a;
    std::sort(v.begin(), v.end());
    v.erase(std::unique(v.begin(), v.end()), v.end());
    for (auto& x : a) x = std::lower_bound(v.begin(), v.end(), x) - v.begin();
    int m = v.size();
    mo mo;
    for (int i = 0; i < q; i++) {
        int l, r;
        std::cin >> l >> r;
        mo.add(l, r);
    }
    atcoder::fenwick_tree<int> ft(m);
    long long inv = 0;
    int size = 0;
    std::vector<long long> ans(q);
    mo.run([&](int i) { inv += ft.sum(0, a[i]); ft.add(a[i], 1); size++; },
           [&](int i) { inv += size - ft.sum(0, a[i] + 1); ft.add(a[i], 1); size++; },
           [&](int i) { ft.add(a[i], -1); size--; inv -= ft.sum(0, a[i]); },
           [&](int i) { ft.add(a[i], -1); size--; inv -= size - ft.sum(0, a[i] + 1); },
           [&](int k) { ans[k] = inv; });
    for (auto x : ans) std::cout << x << '\n';
}

Back to top page