test/yosupo/static_range_inversions_query.test.cpp

View this file on GitHub
Last update: 2024-01-08 16:33:05+09: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>

#include "../../data-structure/fenwick_tree.hpp"
#include "../../misc/compress.hpp"
#include "../../misc/mo.hpp"
using namespace std;
using ll = long long;

struct AddMonoid {
    using T = int;
    static T id() { return 0; }
    static T op(T a, T b) { return a + b; }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    A = Compress<int>(A).compress(A);
    Mo mo(N);
    for (int i = 0; i < Q; ++i) {
        int l, r;
        cin >> l >> r;
        mo.query(l, r);
    }

    FenwickTree<AddMonoid> fw(N);
    ll res = 0;
    vector<ll> ans(Q);
    auto exl = [&](int i) {
        res += fw.prefix_fold(A[i]);
        fw.update(A[i], 1);
    };
    auto shl = [&](int i) {
        res -= fw.prefix_fold(A[i]);
        fw.update(A[i], -1);
    };
    auto exr = [&](int i) {
        res += fw.prefix_fold(N) - fw.prefix_fold(A[i] + 1);
        fw.update(A[i], 1);
    };
    auto shr = [&](int i) {
        res -= fw.prefix_fold(N) - fw.prefix_fold(A[i] + 1);
        fw.update(A[i], -1);
    };
    auto out = [&](int i) { ans[i] = res; };
    mo.run(exl, shl, exr, shr, out);
    for (auto& x : ans) cout << x << "\n";
}

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

#include <bits/stdc++.h>

#line 4 "data-structure/fenwick_tree.hpp"

template <typename M>
class FenwickTree {
    using T = M::T;

   public:
    FenwickTree() = default;
    explicit FenwickTree(int n) : n(n), data(n + 1, M::id()) {}

    T prefix_fold(int i) const {
        T ret = M::id();
        for (; i > 0; i -= i & -i) ret = M::op(ret, data[i]);
        return ret;
    }

    void update(int i, const T& x) {
        for (++i; i <= n; i += i & -i) data[i] = M::op(data[i], x);
    }

    int lower_bound(const T& x) const { return lower_bound(x, std::less<>()); }

    template <typename Compare>
    int lower_bound(const T& x, Compare cmp) const {
        if (!cmp(M::id(), x)) return 0;
        int k = 1;
        while (k * 2 <= n) k <<= 1;
        int i = 0;
        T v = M::id();
        for (; k > 0; k >>= 1) {
            if (i + k > n) continue;
            T nv = M::op(v, data[i + k]);
            if (cmp(nv, x)) {
                v = nv;
                i += k;
            }
        }
        return i + 1;
    }

   private:
    int n;
    std::vector<T> data;
};
#line 4 "misc/compress.hpp"

/**
 * @brief Coordinate Compression
 */
template <typename T>
class Compress {
   public:
    Compress() = default;
    explicit Compress(const std::vector<T>& vs) : xs(vs) {
        std::ranges::sort(xs);
        xs.erase(std::ranges::unique(xs).begin(), xs.end());
    }

    int compress(const T& x) const {
        return std::ranges::lower_bound(xs, x) - xs.begin();
    }

    std::vector<int> compress(const std::vector<T>& vs) const {
        std::vector<int> res(vs.size());
        std::ranges::transform(vs, res.begin(),
                               [&](const T& x) { return compress(x); });
        return res;
    }

    T decompress(int i) const { return xs[i]; }

    int size() const { return xs.size(); }

   private:
    std::vector<T> xs;
};
#line 5 "misc/mo.hpp"

class Mo {
   public:
    Mo() = default;
    explicit Mo(int n) : n(n), cnt(0) {}

    void query(int l, int r) { queries.emplace_back(cnt++, l, r); }

    template <typename ExL, typename ShL, typename ExR, typename ShR,
              typename Out>
    void run(ExL exl, ShL shl, ExR exr, ShR shr, Out out) {
        int s = sqrt(n);
        std::ranges::sort(
            queries, {}, [&](auto& q) { return std::make_pair(q.l / s, q.r); });
        int curL = 0, curR = 0;
        for (auto [id, l, r] : queries) {
            while (curL > l) exl(--curL);
            while (curR < r) exr(curR++);
            while (curL < l) shl(curL++);
            while (curR > r) shr(--curR);
            out(id);
        }
    }

   private:
    struct Query {
        int id, l, r;
    };

    int n, cnt;
    std::vector<Query> queries;
};
#line 8 "test/yosupo/static_range_inversions_query.test.cpp"
using namespace std;
using ll = long long;

struct AddMonoid {
    using T = int;
    static T id() { return 0; }
    static T op(T a, T b) { return a + b; }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    A = Compress<int>(A).compress(A);
    Mo mo(N);
    for (int i = 0; i < Q; ++i) {
        int l, r;
        cin >> l >> r;
        mo.query(l, r);
    }

    FenwickTree<AddMonoid> fw(N);
    ll res = 0;
    vector<ll> ans(Q);
    auto exl = [&](int i) {
        res += fw.prefix_fold(A[i]);
        fw.update(A[i], 1);
    };
    auto shl = [&](int i) {
        res -= fw.prefix_fold(A[i]);
        fw.update(A[i], -1);
    };
    auto exr = [&](int i) {
        res += fw.prefix_fold(N) - fw.prefix_fold(A[i] + 1);
        fw.update(A[i], 1);
    };
    auto shr = [&](int i) {
        res -= fw.prefix_fold(N) - fw.prefix_fold(A[i] + 1);
        fw.update(A[i], -1);
    };
    auto out = [&](int i) { ans[i] = res; };
    mo.run(exl, shl, exr, shr, out);
    for (auto& x : ans) cout << x << "\n";
}