test/hilbert_mo_static_range_inversions_query.test.cpp

• View this file on GitHub
• Last update: 2022-10-01 04:52:28+00:00
• Problem: https://judge.yosupo.jp/problem/static_range_inversions_query

Depends on

• mo/hilbert_mo.hpp

Code

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

#include "mo/hilbert_mo.hpp"
#include <atcoder/fenwicktree>
#include <bits/stdc++.h>

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    int N, Q;
    std::cin >> N >> Q;
    std::vector<int> A(N);
    for (auto &x : A) {
        std::cin >> x;
    }
    std::vector<int> c(A);
    std::sort(c.begin(), c.end());
    c.erase(std::unique(c.begin(), c.end()), c.end());
    for (auto &x : A) {
        auto it = std::lower_bound(c.begin(), c.end(), x);
        x = static_cast<int>(it - c.begin());
    }
    hilbert_mo mo(N);
    for (auto i = 0; i < Q; ++i) {
        int l, r;
        std::cin >> l >> r;
        mo.add(l, r);
    }
    auto s = 0LL;
    auto k = static_cast<int>(c.size());
    atcoder::fenwick_tree<int> ft(k);
    auto add_left = [&](auto i) {
        s += ft.sum(0, A[i]);
        ft.add(A[i], 1);
    };
    auto add_right = [&](auto i) {
        s += ft.sum(A[i] + 1, k);
        ft.add(A[i], 1);
    };
    auto remove_left = [&](auto i) {
        s -= ft.sum(0, A[i]);
        ft.add(A[i], -1);
    };
    auto remove_right = [&](auto i) {
        s -= ft.sum(A[i] + 1, k);
        ft.add(A[i], -1);
    };
    std::vector<long long> ans(Q);
    auto eval = [&](auto i) { ans[i] = s; };
    mo.run(add_left, add_right, remove_left, remove_right, eval);
    for (auto x : ans) {
        std::cout << x << '\n';
    }
}

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

#line 1 "mo/hilbert_mo.hpp"



#include <algorithm>
#include <array>
#include <cassert>
#include <vector>

struct hilbert_mo {
    hilbert_mo(int n) : n_(n), log_(std::__lg(std::max(1, n_)) + 1) {}
    void add(int l, int r) {
        assert(0 <= l && l <= r && r <= n_);
        auto index = static_cast<int>(queries_.size());
        auto order = hilbert_order(l, r, log_, 0);
        queries_.push_back({l, r, index, order});
    }
    template <typename Add, typename Remove, typename Eval>
    void run(Add add, Remove remove, Eval eval) {
        run(add, add, remove, remove, eval);
    }
    template <typename AddLeft, typename AddRight, typename RemoveLeft,
              typename RemoveRight, typename Eval>
    void run(AddLeft add_left, AddRight add_right, RemoveLeft remove_left,
             RemoveRight remove_right, Eval eval) {
        sort(queries_.begin(), queries_.end());
        auto l = 0, r = 0;
        for (auto [left, right, index, order] : queries_) {
            while (left < l) {
                add_left(--l);
            }
            while (r < right) {
                add_right(r++);
            }
            while (l < left) {
                remove_left(l++);
            }
            while (right < r) {
                remove_right(--r);
            }
            eval(index);
        }
    }

private:
    struct query {
        int left, right, index;
        long long order;
        bool operator<(const query &other) const { return order < other.order; }
    };
    long long hilbert_order(int x, int y, int pow, int rotate) const {
        if (pow == 0) {
            return 0;
        }
        auto hpow = 1 << (pow - 1);
        auto seg = (x < hpow) ? ((y < hpow) ? 0 : 3) : ((y < hpow) ? 1 : 2);
        seg = (seg + rotate) & 3;
        const std::array<int, 4> rotate_delta{3, 0, 0, 1};
        auto nx = x & (x ^ hpow), ny = y & (y ^ hpow);
        auto nrot = (rotate + rotate_delta[seg]) & 3;
        auto subsquare_size = static_cast<long long>(1) << (2 * pow - 2);
        auto ans = seg * subsquare_size;
        auto add = hilbert_order(nx, ny, pow - 1, nrot);
        ans += (seg == 1 || seg == 2) ? add : (subsquare_size - add - 1);
        return ans;
    }
    std::vector<query> queries_;
    const int n_, log_;
};


#line 4 "test/hilbert_mo_static_range_inversions_query.test.cpp"
#include <atcoder/fenwicktree>
#include <bits/stdc++.h>

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    int N, Q;
    std::cin >> N >> Q;
    std::vector<int> A(N);
    for (auto &x : A) {
        std::cin >> x;
    }
    std::vector<int> c(A);
    std::sort(c.begin(), c.end());
    c.erase(std::unique(c.begin(), c.end()), c.end());
    for (auto &x : A) {
        auto it = std::lower_bound(c.begin(), c.end(), x);
        x = static_cast<int>(it - c.begin());
    }
    hilbert_mo mo(N);
    for (auto i = 0; i < Q; ++i) {
        int l, r;
        std::cin >> l >> r;
        mo.add(l, r);
    }
    auto s = 0LL;
    auto k = static_cast<int>(c.size());
    atcoder::fenwick_tree<int> ft(k);
    auto add_left = [&](auto i) {
        s += ft.sum(0, A[i]);
        ft.add(A[i], 1);
    };
    auto add_right = [&](auto i) {
        s += ft.sum(A[i] + 1, k);
        ft.add(A[i], 1);
    };
    auto remove_left = [&](auto i) {
        s -= ft.sum(0, A[i]);
        ft.add(A[i], -1);
    };
    auto remove_right = [&](auto i) {
        s -= ft.sum(A[i] + 1, k);
        ft.add(A[i], -1);
    };
    std::vector<long long> ans(Q);
    auto eval = [&](auto i) { ans[i] = s; };
    mo.run(add_left, add_right, remove_left, remove_right, eval);
    for (auto x : ans) {
        std::cout << x << '\n';
    }
}

Back to top page