test/data_structure/Static_Range_Inversions_Query.test.cpp

View this file on GitHub
Last update: 2023-06-30 13:53:37+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 "../../data_structure/fenwick_tree.hpp"
#include "../../misc/mo_algorithm.hpp"
#include "../../template/template.hpp"

using namespace lib;

int main() {
    int n, q;
    std::cin >> n >> q;
    Mo mo(n, q);
    std::vector<int> a(n);
    rep(i, 0, n) std::cin >> a[i];
    auto cp = a;
    std::sort(all(cp));
    cp.erase(unique(all(cp)), cp.end());
    rep(i, 0, n) a[i] = std::lower_bound(all(cp), a[i]) - cp.begin();
    rep(i, 0, q) {
        int l, r;
        std::cin >> l >> r;
        mo.insert(l, r);
    }
    ll ret = 0;
    fenwick_tree<ll> fw(cp.size());
    std::vector<ll> ans(q);
    const auto add_left = [&](int l) -> void {
        ret += fw.prefix_sum(a[l]);
        fw.add(a[l], 1);
    };
    const auto add_right = [&](int r) -> void {
        ret += fw.sum(a[r] + 1, cp.size());
        fw.add(a[r], 1);
    };
    const auto delete_left = [&](int l) -> void {
        ret -= fw.prefix_sum(a[l]);
        fw.add(a[l], -1);
    };
    const auto delete_right = [&](int r) -> void {
        ret -= fw.sum(a[r] + 1, cp.size());
        fw.add(a[r], -1);
    };
    const auto out = [&](int i) -> void { ans[i] = ret; };
    mo.run(add_left, add_right, delete_left, delete_right, out);
    rep(i, 0, q) {
        std::cout << ans[i] << '\n';
    }
}

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

#line 2 "data_structure/fenwick_tree.hpp"

#line 2 "template/template.hpp"

#include <bits/stdc++.h>

#define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++)
#define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--)
#define all(v) v.begin(), v.end()

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <typename T> bool chmin(T &a, const T &b) {
    if (a <= b) return false;
    a = b;
    return true;
}
template <typename T> bool chmax(T &a, const T &b) {
    if (a >= b) return false;
    a = b;
    return true;
}

namespace lib {

using namespace std;

}  // namespace lib

// using namespace lib;
#line 4 "data_structure/fenwick_tree.hpp"

namespace lib {

template <class T> struct fenwick_tree {
  private:
    int n;
    std::vector<T> data;

  public:
    fenwick_tree(int n) : n(n), data(n + 1) {}

    void add(int p, T x) {
        assert(0 <= p && p < n);
        p++;
        for (int i = p; i <= n; i += i & -i) {
            data[i] += x;
        }
    }

    T prefix_sum(int p) const {
        assert(0 <= p && p <= n);
        T ret = 0;
        for (int i = p; i > 0; i -= i & -i) {
            ret += data[i];
        }
        return ret;
    }

    T sum(int l, int r) const {
        return prefix_sum(r) - prefix_sum(l);
    }
};

}  // namespace lib
#line 2 "misc/mo_algorithm.hpp"

#line 4 "misc/mo_algorithm.hpp"

namespace lib {

struct Mo {
    int width;
    vector<int> left, right, order;

    Mo(int N = 1, int Q = 1) : order(Q) {
        width = max<int>(1, 1.0 * N / max<double>(1.0, sqrt(Q * 2.0 / 3.0)));
        iota(begin(order), end(order), 0);
    }

    void insert(int l, int r) { /* [l, r) */
        left.emplace_back(l);
        right.emplace_back(r);
    }

    template <typename AL, typename AR, typename DL, typename DR, typename REM>
    void run(const AL &add_left, const AR &add_right, const DL &delete_left,
             const DR &delete_right, const REM &rem) {
        assert(left.size() == order.size());
        sort(begin(order), end(order), [&](int a, int b) {
            int ablock = left[a] / width, bblock = left[b] / width;
            if (ablock != bblock) return ablock < bblock;
            if (ablock & 1) return right[a] < right[b];
            return right[a] > right[b];
        });
        int nl = 0, nr = 0;
        for (auto idx : order) {
            while (nl > left[idx]) add_left(--nl);
            while (nr < right[idx]) add_right(nr++);
            while (nl < left[idx]) delete_left(nl++);
            while (nr > right[idx]) delete_right(--nr);
            rem(idx);
        }
    }
};

}  // namespace lib
#line 6 "test/data_structure/Static_Range_Inversions_Query.test.cpp"

using namespace lib;

int main() {
    int n, q;
    std::cin >> n >> q;
    Mo mo(n, q);
    std::vector<int> a(n);
    rep(i, 0, n) std::cin >> a[i];
    auto cp = a;
    std::sort(all(cp));
    cp.erase(unique(all(cp)), cp.end());
    rep(i, 0, n) a[i] = std::lower_bound(all(cp), a[i]) - cp.begin();
    rep(i, 0, q) {
        int l, r;
        std::cin >> l >> r;
        mo.insert(l, r);
    }
    ll ret = 0;
    fenwick_tree<ll> fw(cp.size());
    std::vector<ll> ans(q);
    const auto add_left = [&](int l) -> void {
        ret += fw.prefix_sum(a[l]);
        fw.add(a[l], 1);
    };
    const auto add_right = [&](int r) -> void {
        ret += fw.sum(a[r] + 1, cp.size());
        fw.add(a[r], 1);
    };
    const auto delete_left = [&](int l) -> void {
        ret -= fw.prefix_sum(a[l]);
        fw.add(a[l], -1);
    };
    const auto delete_right = [&](int r) -> void {
        ret -= fw.sum(a[r] + 1, cp.size());
        fw.add(a[r], -1);
    };
    const auto out = [&](int i) -> void { ans[i] = ret; };
    mo.run(add_left, add_right, delete_left, delete_right, out);
    rep(i, 0, q) {
        std::cout << ans[i] << '\n';
    }
}