その他/Mo's algorithm
(test/misc/mo.test.cpp)

• View this file on GitHub
• Last update: 2023-02-25 16:35:06+09:00
• Problem: https://judge.yosupo.jp/problem/static_range_inversions_query

Depends on

• Fenwick tree (binary indexed tree) (include/emthrm/data_structure/fenwick_tree/fenwick_tree.hpp)
• Mo's algorithm (include/emthrm/misc/mo.hpp)

Code

/*
 * @title その他/Mo's algorithm
 *
 * verification-helper: PROBLEM https://judge.yosupo.jp/problem/static_range_inversions_query
 */

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

#include "emthrm/data_structure/fenwick_tree/fenwick_tree.hpp"
#include "emthrm/misc/mo.hpp"

std::vector<int> a;
long long inv = 0;
int l = 0, r = 0, m;
constexpr int M = 100000;
emthrm::FenwickTree<int> bit(M);

void emthrm::Mo::add(const int idx) const {
  if (idx + 1 == l) {
    inv += bit.sum(0, a[idx]);
    --l;
  } else if (idx == r) {
    inv += bit.sum(a[idx] + 1, m);
    ++r;
  }
  bit.add(a[idx], 1);
}

void emthrm::Mo::del(const int idx) const {
  if (idx == l) {
    inv -= bit.sum(0, a[idx]);
    ++l;
  } else if (idx + 1 == r) {
    inv -= bit.sum(a[idx] + 1, m);
    --r;
  }
  bit.add(a[idx], -1);
}

int main() {
  int n, q;
  std::cin >> n >> q;
  a.resize(n);
  for (int i = 0; i < n; ++i) {
    std::cin >> a[i];
  }
  std::vector<int> tmp = a;
  std::sort(tmp.begin(), tmp.end());
  tmp.erase(std::unique(tmp.begin(), tmp.end()), tmp.end());
  m = tmp.size();
  for (int i = 0; i < n; ++i) {
    a[i] = std::distance(tmp.begin(),
                         std::lower_bound(tmp.begin(), tmp.end(), a[i]));
  }
  std::vector<int> ls(q), rs(q);
  for (int i = 0; i < q; ++i) {
    std::cin >> ls[i] >> rs[i];
  }
  emthrm::Mo mo(ls, rs);
  std::vector<long long> ans(q);
  for (int i = 0; i < q; ++i) {
    const int idx = mo.process();
    ans[idx] = inv;
  }
  for (int i = 0; i < q; ++i) {
    std::cout << ans[i] << '\n';
  }
  return 0;
}

#line 1 "test/misc/mo.test.cpp"
/*
 * @title その他/Mo's algorithm
 *
 * verification-helper: PROBLEM https://judge.yosupo.jp/problem/static_range_inversions_query
 */

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

#line 1 "include/emthrm/data_structure/fenwick_tree/fenwick_tree.hpp"



#include <bit>
#line 6 "include/emthrm/data_structure/fenwick_tree/fenwick_tree.hpp"

namespace emthrm {

template <typename Abelian>
struct FenwickTree {
  explicit FenwickTree(const int n, const Abelian ID = 0)
      : n(n), ID(ID), data(n, ID) {}

  void add(int idx, const Abelian val) {
    for (; idx < n; idx |= idx + 1) {
      data[idx] += val;
    }
  }

  Abelian sum(int idx) const {
    Abelian res = ID;
    for (--idx; idx >= 0; idx = (idx & (idx + 1)) - 1) {
      res += data[idx];
    }
    return res;
  }

  Abelian sum(const int left, const int right) const {
    return left < right ? sum(right) - sum(left) : ID;
  }

  Abelian operator[](const int idx) const { return sum(idx, idx + 1); }

  int lower_bound(Abelian val) const {
    if (val <= ID) [[unlikely]] return 0;
    int res = 0;
    for (int mask = std::bit_ceil(static_cast<unsigned int>(n + 1)) >> 1;
         mask > 0; mask >>= 1) {
      const int idx = res + mask - 1;
      if (idx < n && data[idx] < val) {
        val -= data[idx];
        res += mask;
      }
    }
    return res;
  }

 private:
  const int n;
  const Abelian ID;
  std::vector<Abelian> data;
};

}  // namespace emthrm


#line 1 "include/emthrm/misc/mo.hpp"



#line 5 "include/emthrm/misc/mo.hpp"
#include <cmath>
#include <numeric>
#line 8 "include/emthrm/misc/mo.hpp"

namespace emthrm {

struct Mo {
  explicit Mo(const std::vector<int>& ls, const std::vector<int>& rs)
      : n(ls.size()), ptr(0), nl(0), nr(0), ls(ls), rs(rs) {
    const int width = std::round(std::sqrt(n));
    order.resize(n);
    std::iota(order.begin(), order.end(), 0);
    std::sort(order.begin(), order.end(),
              [&ls, &rs, width](const int a, const int b) -> bool {
                  if (ls[a] / width != ls[b] / width) return ls[a] < ls[b];
                  return (ls[a] / width) & 1 ? rs[a] < rs[b] : rs[a] > rs[b];
              });
  }

  int process() {
    if (ptr == n) [[unlikely]] return -1;
    const int id = order[ptr++];
    while (ls[id] < nl) add(--nl);
    while (nr < rs[id]) add(nr++);
    while (nl < ls[id]) del(nl++);
    while (rs[id] < nr) del(--nr);
    return id;
  }

  void add(const int idx) const;

  void del(const int idx) const;

 private:
  const int n;
  int ptr, nl, nr;
  std::vector<int> ls, rs, order;
};

}  // namespace emthrm


#line 14 "test/misc/mo.test.cpp"

std::vector<int> a;
long long inv = 0;
int l = 0, r = 0, m;
constexpr int M = 100000;
emthrm::FenwickTree<int> bit(M);

void emthrm::Mo::add(const int idx) const {
  if (idx + 1 == l) {
    inv += bit.sum(0, a[idx]);
    --l;
  } else if (idx == r) {
    inv += bit.sum(a[idx] + 1, m);
    ++r;
  }
  bit.add(a[idx], 1);
}

void emthrm::Mo::del(const int idx) const {
  if (idx == l) {
    inv -= bit.sum(0, a[idx]);
    ++l;
  } else if (idx + 1 == r) {
    inv -= bit.sum(a[idx] + 1, m);
    --r;
  }
  bit.add(a[idx], -1);
}

int main() {
  int n, q;
  std::cin >> n >> q;
  a.resize(n);
  for (int i = 0; i < n; ++i) {
    std::cin >> a[i];
  }
  std::vector<int> tmp = a;
  std::sort(tmp.begin(), tmp.end());
  tmp.erase(std::unique(tmp.begin(), tmp.end()), tmp.end());
  m = tmp.size();
  for (int i = 0; i < n; ++i) {
    a[i] = std::distance(tmp.begin(),
                         std::lower_bound(tmp.begin(), tmp.end(), a[i]));
  }
  std::vector<int> ls(q), rs(q);
  for (int i = 0; i < q; ++i) {
    std::cin >> ls[i] >> rs[i];
  }
  emthrm::Mo mo(ls, rs);
  std::vector<long long> ans(q);
  for (int i = 0; i < q; ++i) {
    const int idx = mo.process();
    ans[idx] = inv;
  }
  for (int i = 0; i < q; ++i) {
    std::cout << ans[i] << '\n';
  }
  return 0;
}

Back to top page