test/yosupo/ds/static_range_inversions_query.test.cpp

View this file on GitHub
Last update: 2025-09-24 21:58:49+07:00
Problem: https://judge.yosupo.jp/problem/static_range_inversions_query

Depends on

Code

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

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

#include "other/compressor.hpp"
#include "other/mo.hpp"

struct fenwick_tree {
    int n;
    vector<int> t;

    fenwick_tree(int _n) : n(_n), t(n + 1) {}

    void add(int p, int d) {
        for (p++; p <= n; p += p & -p) t[p] += d;
    }
    int pref(int r) const {
        int s = 0;
        for (; r; r &= r - 1) s += t[r];
        return s;
    }
    int suf(int l) const { return pref(n) - pref(l); }
    int sum(int l, int r) const { return pref(r) - pref(l); }
};

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, q;
    cin >> n >> q;
    Compressor comp;
    vector<int> a(n);
    for (int &i : a) cin >> i;
    comp.push(a);
    int m = comp.build();
    vector<pair<int, int>> qs(q);
    for (auto &[l, r] : qs) cin >> l >> r;
    Mo mo(n, move(qs));

    int64_t inv = 0;
    fenwick_tree tr(m);
    vector<int64_t> ans(q);
    mo.run(
        [&](int i) { ans[i] = inv; },
        [&](int i) { inv += tr.pref(a[i]), tr.add(a[i], +1); },
        [&](int i) { inv -= tr.pref(a[i]), tr.add(a[i], -1); },
        [&](int i) { inv += tr.suf(a[i] + 1), tr.add(a[i], +1); },
        [&](int i) { inv -= tr.suf(a[i] + 1), tr.add(a[i], -1); }
    );
    for (auto i : ans) cout << i << "\n";
}

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

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

#line 2 "other/compressor.hpp"

// clang-format off
template<class T = int> struct Compressor {
    vector<reference_wrapper<T>> val;
    vector<T> og;

    Compressor(int n = 0) { val.reserve(n); }

    template<class... Ts> void push(Ts &...x) { (_push(x), ...); }
    int build() {
        sort(begin(val), end(val));
        og.reserve(val.size());
        T id = -1;
        for (auto x : val) {
            if (og.empty() || og.back() != x) id++, og.push_back(x);
            x.get() = id;
        }
        og.shrink_to_fit();
        return size();
    }
    int size() const { return (int)og.size(); }
    T operator[](int i) const { return og[i]; }
    int operator()(T x) const { return int(lower_bound(begin(og), end(og), x) - begin(og)); }
    bool find(T x) const { return binary_search(begin(og), end(og), x); }

  private:
    void _push(T &x) { val.push_back(x); }
    void _push(pair<T, T> &p) { push(p.first, p.second); }
    template<class V> void _push(V &a) { for (auto &x : a) _push(x); }
};
// clang-format on
#line 2 "other/mo.hpp"

struct Mo {
    int q;
    const int B;
    vector<int> qi;
    vector<pair<int, int>> qs;

    int l = 0, r = 0;

    Mo(int n, const vector<pair<int, int>> &_qs) :
        q((int)_qs.size()), B(blk_sz(n, q)), qi(q), qs(_qs) {
        iota(begin(qi), end(qi), 0);
        sort(begin(qi), end(qi), [&](int i, int j) {
            auto [li, ri] = qs[i];
            auto [lj, rj] = qs[j];
            int bi = li / B, bj = lj / B;
            if (bi != bj) return bi < bj;
            if (ri != rj) return (bi & 1) != (ri < rj);
            return li < lj;
        });
    }

    template<class Eval, class AL, class DL, class AR, class DR>
    void run(Eval eval, AL add_l, DL del_l, AR add_r, DR del_r) {
        for (int i : qi) {
            auto [ql, qr] = qs[i];
            while (ql < l) add_l(--l);
            while (r < qr) add_r(r++);
            while (l < ql) del_l(l++);
            while (qr < r) del_r(--r);
            eval(i);
        }
    }
    template<class Eval, class Add, class Del>
    void run(Eval eval, Add add, Del del) {
        run(eval, add, del, add, del);
    }

  private:
    static int blk_sz(int n, int q) {
        return max(1, int(n / max<double>(1, sqrt(q * 2.0 / 3.0))));
    }
};
#line 8 "test/yosupo/ds/static_range_inversions_query.test.cpp"

struct fenwick_tree {
    int n;
    vector<int> t;

    fenwick_tree(int _n) : n(_n), t(n + 1) {}

    void add(int p, int d) {
        for (p++; p <= n; p += p & -p) t[p] += d;
    }
    int pref(int r) const {
        int s = 0;
        for (; r; r &= r - 1) s += t[r];
        return s;
    }
    int suf(int l) const { return pref(n) - pref(l); }
    int sum(int l, int r) const { return pref(r) - pref(l); }
};

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, q;
    cin >> n >> q;
    Compressor comp;
    vector<int> a(n);
    for (int &i : a) cin >> i;
    comp.push(a);
    int m = comp.build();
    vector<pair<int, int>> qs(q);
    for (auto &[l, r] : qs) cin >> l >> r;
    Mo mo(n, move(qs));

    int64_t inv = 0;
    fenwick_tree tr(m);
    vector<int64_t> ans(q);
    mo.run(
        [&](int i) { ans[i] = inv; },
        [&](int i) { inv += tr.pref(a[i]), tr.add(a[i], +1); },
        [&](int i) { inv -= tr.pref(a[i]), tr.add(a[i], -1); },
        [&](int i) { inv += tr.suf(a[i] + 1), tr.add(a[i], +1); },
        [&](int i) { inv -= tr.suf(a[i] + 1), tr.add(a[i], -1); }
    );
    for (auto i : ans) cout << i << "\n";
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	5 ms	4 MB
g++	max_00	AC	717 ms	8 MB
g++	max_01	AC	754 ms	8 MB
g++	max_02	AC	740 ms	8 MB
g++	random_00	AC	107 ms	6 MB
g++	random_01	AC	204 ms	5 MB
g++	random_02	AC	260 ms	6 MB
g++	small_a_00	AC	390 ms	7 MB
g++	small_n_00	AC	8 ms	4 MB
g++	small_n_01	AC	18 ms	5 MB
g++	small_n_02	AC	16 ms	5 MB
g++	small_n_03	AC	13 ms	4 MB
g++	small_n_04	AC	8 ms	4 MB
clang++	example_00	AC	5 ms	4 MB
clang++	max_00	AC	709 ms	8 MB
clang++	max_01	AC	716 ms	8 MB
clang++	max_02	AC	709 ms	8 MB
clang++	random_00	AC	118 ms	6 MB
clang++	random_01	AC	219 ms	5 MB
clang++	random_02	AC	283 ms	6 MB
clang++	small_a_00	AC	425 ms	7 MB
clang++	small_n_00	AC	8 ms	4 MB
clang++	small_n_01	AC	18 ms	5 MB
clang++	small_n_02	AC	15 ms	5 MB
clang++	small_n_03	AC	12 ms	4 MB
clang++	small_n_04	AC	8 ms	4 MB