matsutaku-library
This documentation is automatically generated by competitive-verifier/competitive-verifier
test/yosupo/static_range_inversions_query-mo.test.cpp
- View this file on GitHub
- Last update: 2024-07-11 22:21:57+09:00
- Problem: https://judge.yosupo.jp/problem/static_range_inversions_query
Code
#define PROBLEM "https://judge.yosupo.jp/problem/static_range_inversions_query"
#include "include/mtl/compress_int.hpp"
#include "include/mtl/mo.hpp"
#include "include/mtl/fenwick_tree.hpp"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
constexpr int N = 1e5;
int main() {
int n,q; cin>>n>>q;
vector<int> A(n);
for (int i = 0; i < n; i++) {
cin>>A[i];
}
auto id = Compressor<int>::compress(A.begin(), A.end());
auto k = id.size();
MoSolver mo;
for (int i = 0; i < q; i++) {
int l,r; cin>>l>>r;
mo.add_segment(l, r);
}
FenwickTree<int> D(k);
vector<lint> ans(q);
lint inv_sum = 0;
auto _pushl = [&](int i) {
int vi = id[A[i]];
inv_sum += D.sum(0, vi);
D.add(vi, 1);
};
auto _pushr = [&](int i) {
int vi = id[A[i]];
inv_sum += D.sum(vi+1, k);
D.add(vi, 1);
};
auto _popl = [&](int i) {
int vi = id[A[i]];
inv_sum -= D.sum(0, vi);
D.add(vi, -1);
};
auto _popr = [&](int i) {
int vi = id[A[i]];
inv_sum -= D.sum(vi+1, k);
D.add(vi, -1);
};
auto rem = [&](int t) {
ans[t] = inv_sum;
};
mo.solve(_pushl, _pushr, _popl, _popr, rem);
for (lint v : ans) cout << v << endl;
}
#line 1 "test/yosupo/static_range_inversions_query-mo.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/static_range_inversions_query"
#line 2 "include/mtl/compress_int.hpp"
#include <set>
#include <unordered_map>
#include <vector>
#include <algorithm>
template<class T, class MapContainer=std::unordered_map<T, int>>
class Compressor {
public:
using map_type = MapContainer;
private:
std::vector<T> vs;
public:
Compressor() = default;
template<typename It>
Compressor(It begin, It end) : vs(begin, end) {}
void clear() { vs.clear(); }
void add(T x) {
vs.push_back(x);
}
template<typename It>
void add(It begin, It end) {
vs.insert(vs.end(), begin, end);
}
map_type release() {
std::sort(vs.begin(), vs.end());
vs.erase(std::unique(vs.begin(), vs.end()), vs.end());
map_type mp;
mp.reserve(vs.size());
int k = 0;
for (auto v : vs) mp[v] = k++;
return mp;
}
std::pair<map_type, std::vector<T>> release_tie() {
return std::make_pair(release(), std::move(vs));
}
template<typename It>
static map_type compress(It begin, It end) {
return Compressor(begin, end).release();
}
};
#line 3 "include/mtl/mo.hpp"
#include <numeric>
#include <cmath>
#include <tuple>
#line 7 "include/mtl/mo.hpp"
#include <iostream>
#include <cassert>
/**
* @brief Mo's algorithm: solve offline segment queries on a sequence
* @note This implementation is optimized by noshi's idea
* complexity of N sqrt(Q) + O(N).
* - 定数倍が最適な Mo's Algorithm. noshi91のメモ. 2023/04/13.
* https://noshi91.hatenablog.com/entry/2023/04/13/224811
* @note Mo's algorithm with rollback is based on snuke's idea
* - Mo's algorithm とその上位互換の話. あなたは嘘つきですかと聞かれたら「YES」と答えるブログ. 2016/07/01.
* https://snuke.hatenablog.com/entry/2016/07/01/000000
*/
struct MoSolver {
std::vector<std::tuple<int, int, int>> segs;
int q = 0;
void add_segment(int l, int r) {
assert(l <= r);
segs.emplace_back(q++, l, r);
}
void calc_mos_move(std::vector<int>& dst) const {
using std::get;
int n = 0;
for (auto s:segs)
n = std::max(n, get<2>(s));
auto rtq = std::sqrt(q);
int b = std::ceil((double)n / rtq);
auto bf = b-b/2;
auto get_bo = [&](int x) {
if (x < bf) return 0;
return (x-bf)/b+1;
};
auto EvenComp = [&](int u, int v) {
auto &s = segs[u], &t = segs[v];
auto ls = get<1>(s), rs = get<2>(s), lt = get<1>(t), rt = get<2>(t);
auto bs = ls / b, bt = lt / b;
return bs != bt ? ls < lt : (bs%2==0 ? rs < rt : rs > rt);
};
auto OddComp = [&](int u, int v) {
auto &s = segs[u], &t = segs[v];
auto ls = get<1>(s), rs = get<2>(s), lt = get<1>(t), rt = get<2>(t);
auto bs = get_bo(ls), bt = get_bo(lt);
return bs != bt ? ls < lt : (bs%2==0 ? rs < rt : rs > rt);
};
auto& IE = dst;
IE.resize(q);
std::iota(IE.begin(), IE.end(), 0);
std::sort(IE.begin(), IE.end(),
EvenComp);
auto IO = IE;
std::sort(IO.begin(), IO.end(),
OddComp);
auto move_distance = [&](const std::vector<int>& ids) {
long long d = 0;
for (int i = 0; i < q-1; i++) {
int j = ids[i], k = ids[i+1];
d += std::abs(get<1>(segs[j]) - get<1>(segs[k]));
d += std::abs(get<2>(segs[j]) - get<2>(segs[k]));
}
return d;
};
if (move_distance(IE) > move_distance(IO))
dst = std::move(IO); // IE is reference of dst
}
template<class PUSH_L, class PUSH_R, class POP_L, class POP_R, class REM>
void solve(PUSH_L pushl, PUSH_R pushr, POP_L popl, POP_R popr, REM rem) const {
if (q == 0) return;
std::vector<int> I;
calc_mos_move(I);
int _l = 0, _r = 0;
for (int i:I) {
int t,l,r;
std::tie(t,l,r) = segs[i];
while (l < _l)
pushl(--_l);
while (_r < r)
pushr(_r++);
while (_l < l)
popl(_l++);
while (r < _r)
popr(--_r);
rem(t);
}
}
template<class Block, class Bend>
long long calc_mos_rollback_move(std::vector<int>& idx, std::vector<std::pair<int,int>>& blocks, Block block, Bend bend) const {
std::sort(idx.begin(), idx.end(), [&](auto a, auto b) {
auto [ta, la, ra] = segs[a];
auto [tb, lb, rb] = segs[b];
auto ba = block(la), bb = block(lb);
return ba != bb ? la < lb : ra < rb;
});
long long dist = 0;
int cb = -1;
int _l = 0, _r = 0;
for (size_t i = 0; i < idx.size(); i++) {
auto [t,l,r] = segs[idx[i]];
auto bi = block(l);
auto be = bend(bi);
blocks[i] = std::make_pair(bi, be);
if (bi != cb) {
_r = be;
cb = bi;
}
dist += r-_r;
_r = r;
_l = be;
dist += _l-l;
}
return dist;
}
template<class PUSH_L, class PUSH_R, class REM,
class INIT, class SNAPSHOT, class ROLLBACK>
void solve_rollback(PUSH_L pushl, PUSH_R pushr, REM rem,
INIT init, SNAPSHOT snapshot, ROLLBACK rollback) const {
if (q == 0) return;
int n = 0;
for (auto s:segs)
n = std::max(n, std::get<2>(s));
// * (2|xi-c|+b/2)q, |xi-c| < b/2, (mean |xi-c| = b/4) -> bq
// * min bq + n^2/b,
// from AMGM, bq = n^2/b => b^2 = n^2 /q => b = n / sqrt(q)
// * F = (bq + n^2/b)/2
// = bq
// = n sqrt(q)
const int b = std::ceil((double)n / std::sqrt(q));
std::vector<int> J;
for (int i = 0; i < q; i++) {
auto [t,l,r] = segs[i];
if (r-l < b) {
init();
for (int j = l; j < r; j++)
pushr(j);
rem(t);
} else {
J.push_back(i);
}
}
std::vector<std::pair<int,int>> B(J.size());
{
auto& b_even = B;
auto block_even = [&](int x) {
return x / b;
};
auto bend_even = [&](int bi) {
return (bi+1)*b;
};
auto dist_e = calc_mos_rollback_move(J, b_even, block_even, bend_even);
auto K = J;
auto b_odd = B;
const auto bf = b-b/2;
auto block_odd = [&](int x) {
return x < bf ? 0 : (x-bf)/b+1;
};
auto bend_odd = [&](int bi) {
return bf+bi*b;
};
auto dist_o = calc_mos_rollback_move(K, b_odd, block_odd, bend_odd);
if (dist_e > dist_o) {
J = std::move(K);
B = std::move(b_odd);
}
}
int cb = -1;
int _l = 0, _r = 0;
for (auto it = J.begin(); it != J.end(); ++it) {
auto [t,l,r] = segs[*it];
auto [bi,be] = B[it-J.begin()];
if (bi != cb) {
init();
_r = be;
cb = bi;
}
assert(_r <= r);
while (_r < r) {
pushr(_r++);
}
snapshot();
_l = be;
assert(l <= _l);
assert(_l-l <= b);
while (l < _l) {
pushl(--_l);
}
rem(t);
rollback();
}
}
};
#line 2 "include/mtl/bit_manip.hpp"
#include <cstdint>
#line 4 "include/mtl/bit_manip.hpp"
#if __cplusplus >= 202002L
#ifndef MTL_CPP20
#define MTL_CPP20
#endif
#include <bit>
#endif
namespace bm {
/// Count 1s for each 8 bits
inline constexpr uint64_t popcnt_e8(uint64_t x) {
x = (x & 0x5555555555555555) + ((x>>1) & 0x5555555555555555);
x = (x & 0x3333333333333333) + ((x>>2) & 0x3333333333333333);
x = (x & 0x0F0F0F0F0F0F0F0F) + ((x>>4) & 0x0F0F0F0F0F0F0F0F);
return x;
}
/// Count 1s
inline constexpr unsigned popcnt(uint64_t x) {
#ifdef MTL_CPP20
return std::popcount(x);
#else
return (popcnt_e8(x) * 0x0101010101010101) >> 56;
#endif
}
/// Alias to mtl::popcnt(x)
constexpr unsigned popcount(uint64_t x) {
return popcnt(x);
}
/// Count trailing 0s. s.t. *11011000 -> 3
inline constexpr unsigned ctz(uint64_t x) {
#ifdef MTL_CPP20
return std::countr_zero(x);
#else
return popcnt((x & (-x)) - 1);
#endif
}
/// Alias to mtl::ctz(x)
constexpr unsigned countr_zero(uint64_t x) {
return ctz(x);
}
/// Count trailing 1s. s.t. *11011011 -> 2
inline constexpr unsigned cto(uint64_t x) {
#ifdef MTL_CPP20
return std::countr_one(x);
#else
return ctz(~x);
#endif
}
/// Alias to mtl::cto(x)
constexpr unsigned countr_one(uint64_t x) {
return cto(x);
}
inline constexpr unsigned ctz8(uint8_t x) {
return x == 0 ? 8 : popcnt_e8((x & (-x)) - 1);
}
/// [00..0](8bit) -> 0, [**..*](not only 0) -> 1
inline constexpr uint8_t summary(uint64_t x) {
constexpr uint64_t hmask = 0x8080808080808080ull;
constexpr uint64_t lmask = 0x7F7F7F7F7F7F7F7Full;
auto a = x & hmask;
auto b = x & lmask;
b = hmask - b;
b = ~b;
auto c = (a | b) & hmask;
c *= 0x0002040810204081ull;
return uint8_t(c >> 56);
}
/// Extract target area of bits
inline constexpr uint64_t bextr(uint64_t x, unsigned start, unsigned len) {
uint64_t mask = len < 64 ? (1ull<<len)-1 : 0xFFFFFFFFFFFFFFFFull;
return (x >> start) & mask;
}
/// 00101101 -> 00111111 -count_1s-> 6
inline constexpr unsigned log2p1(uint8_t x) {
if (x & 0x80)
return 8;
uint64_t p = uint64_t(x) * 0x0101010101010101ull;
p -= 0x8040201008040201ull;
p = ~p & 0x8080808080808080ull;
p = (p >> 7) * 0x0101010101010101ull;
p >>= 56;
return p;
}
/// 00101100 -mask_mssb-> 00100000 -to_index-> 5
inline constexpr unsigned mssb8(uint8_t x) {
assert(x != 0);
return log2p1(x) - 1;
}
/// 00101100 -mask_lssb-> 00000100 -to_index-> 2
inline constexpr unsigned lssb8(uint8_t x) {
assert(x != 0);
return popcnt_e8((x & -x) - 1);
}
/// Count leading 0s. 00001011... -> 4
inline constexpr unsigned clz(uint64_t x) {
#ifdef MTL_CPP20
return std::countl_zero(x);
#else
if (x == 0)
return 64;
auto i = mssb8(summary(x));
auto j = mssb8(bextr(x, 8 * i, 8));
return 63 - (8 * i + j);
#endif
}
/// Alias to mtl::clz(x)
constexpr unsigned countl_zero(uint64_t x) {
return clz(x);
}
/// Count leading 1s. 11110100... -> 4
inline constexpr unsigned clo(uint64_t x) {
#ifdef MTL_CPP20
return std::countl_one(x);
#else
return clz(~x);
#endif
}
/// Alias to mtl::clo(x)
constexpr unsigned countl_one(uint64_t x) {
return clo(x);
}
inline constexpr unsigned clz8(uint8_t x) {
return x == 0 ? 8 : 7 - mssb8(x);
}
inline constexpr uint64_t bit_reverse(uint64_t x) {
x = ((x & 0x00000000FFFFFFFF) << 32) | ((x & 0xFFFFFFFF00000000) >> 32);
x = ((x & 0x0000FFFF0000FFFF) << 16) | ((x & 0xFFFF0000FFFF0000) >> 16);
x = ((x & 0x00FF00FF00FF00FF) << 8) | ((x & 0xFF00FF00FF00FF00) >> 8);
x = ((x & 0x0F0F0F0F0F0F0F0F) << 4) | ((x & 0xF0F0F0F0F0F0F0F0) >> 4);
x = ((x & 0x3333333333333333) << 2) | ((x & 0xCCCCCCCCCCCCCCCC) >> 2);
x = ((x & 0x5555555555555555) << 1) | ((x & 0xAAAAAAAAAAAAAAAA) >> 1);
return x;
}
/// Check if x is power of 2. 00100000 -> true, 00100001 -> false
constexpr bool has_single_bit(uint64_t x) noexcept {
#ifdef MTL_CPP20
return std::has_single_bit(x);
#else
return x != 0 && (x & (x - 1)) == 0;
#endif
}
/// Bit width needs to represent x. 00110110 -> 6
constexpr int bit_width(uint64_t x) noexcept {
#ifdef MTL_CPP20
return std::bit_width(x);
#else
return 64 - clz(x);
#endif
}
/// Ceil power of 2. 00110110 -> 01000000
constexpr uint64_t bit_ceil(uint64_t x) {
#ifdef MTL_CPP20
return std::bit_ceil(x);
#else
if (x == 0) return 1;
return 1ull << bit_width(x - 1);
#endif
}
/// Floor power of 2. 00110110 -> 00100000
constexpr uint64_t bit_floor(uint64_t x) {
#ifdef MTL_CPP20
return std::bit_floor(x);
#else
if (x == 0) return 0;
return 1ull << (bit_width(x) - 1);
#endif
}
} // namespace bm
#line 3 "include/mtl/fenwick_tree.hpp"
#include <cstddef>
#line 5 "include/mtl/fenwick_tree.hpp"
template <class T>
class FenwickTree {
private:
std::vector<T> tree_;
public:
FenwickTree() = default;
explicit FenwickTree(size_t size) : tree_(size+1) {}
size_t size() const { return tree_.size()-1; }
template <class Iter>
explicit FenwickTree(Iter begin, Iter end) : FenwickTree(std::distance(begin, end)) {
size_t i = 1;
for (auto it = begin; it != end; ++it) {
tree_[i] = tree_[i] + *it;
auto j = i + (i&(-i));
if (j < tree_.size())
tree_[j] = tree_[j] + tree_[i];
++i;
}
}
template<class V>
void add(size_t index, const V& x) {
for (size_t i = index+1; i < tree_.size(); i += i&(-i))
tree_[i] = tree_[i] + x;
}
T sum(size_t index) const {
T sum = 0;
for (size_t i = index+1; i > 0; i -= i&(-i))
sum = sum + tree_[i];
return sum;
}
T range_sum(size_t l, size_t r) const {
auto sl = l > 0 ? sum(l-1) : 0;
auto sr = r > 0 ? sum(r-1) : 0;
return sr - sl;
}
/// @brief Alias of range_sum(l, r)
T sum(size_t l, size_t r) const {
return range_sum(l, r);
}
template<class V>
size_t lower_bound(const V& _sum) const {
size_t ret = 0;
T s = 0;
for (int k = 63-bm::clz(size()); k >= 0; k--) {
size_t j = ret | (1ull<<k);
if (j < tree_.size() and s + tree_[j] < _sum) {
s = s + tree_[j];
ret = j;
}
}
return ret;
}
};
#line 5 "test/yosupo/static_range_inversions_query-mo.test.cpp"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
constexpr int N = 1e5;
int main() {
int n,q; cin>>n>>q;
vector<int> A(n);
for (int i = 0; i < n; i++) {
cin>>A[i];
}
auto id = Compressor<int>::compress(A.begin(), A.end());
auto k = id.size();
MoSolver mo;
for (int i = 0; i < q; i++) {
int l,r; cin>>l>>r;
mo.add_segment(l, r);
}
FenwickTree<int> D(k);
vector<lint> ans(q);
lint inv_sum = 0;
auto _pushl = [&](int i) {
int vi = id[A[i]];
inv_sum += D.sum(0, vi);
D.add(vi, 1);
};
auto _pushr = [&](int i) {
int vi = id[A[i]];
inv_sum += D.sum(vi+1, k);
D.add(vi, 1);
};
auto _popl = [&](int i) {
int vi = id[A[i]];
inv_sum -= D.sum(0, vi);
D.add(vi, -1);
};
auto _popr = [&](int i) {
int vi = id[A[i]];
inv_sum -= D.sum(vi+1, k);
D.add(vi, -1);
};
auto rem = [&](int t) {
ans[t] = inv_sum;
};
mo.solve(_pushl, _pushr, _popl, _popr, rem);
for (lint v : ans) cout << v << endl;
}
Test cases
| Env | Name | Status | Elapsed | Memory |
|---|---|---|---|---|
| g++ | example_00 |
AC |
6 ms | 3 MB |
| g++ | max_00 |
AC |
1974 ms | 11 MB |
| g++ | max_01 |
AC |
1949 ms | 11 MB |
| g++ | max_02 |
AC |
1957 ms | 11 MB |
| g++ | random_00 |
AC |
311 ms | 6 MB |
| g++ | random_01 |
AC |
617 ms | 7 MB |
| g++ | random_02 |
AC |
794 ms | 7 MB |
| g++ | small_a_00 |
AC |
688 ms | 6 MB |
| g++ | small_n_00 |
AC |
24 ms | 4 MB |
| g++ | small_n_01 |
AC |
93 ms | 5 MB |
| g++ | small_n_02 |
AC |
73 ms | 5 MB |
| g++ | small_n_03 |
AC |
51 ms | 4 MB |
| g++ | small_n_04 |
AC |
24 ms | 4 MB |
| clang++ | example_00 |
AC |
6 ms | 4 MB |
| clang++ | max_00 |
AC |
1999 ms | 11 MB |
| clang++ | max_01 |
AC |
1980 ms | 11 MB |
| clang++ | max_02 |
AC |
1996 ms | 11 MB |
| clang++ | random_00 |
AC |
316 ms | 6 MB |
| clang++ | random_01 |
AC |
617 ms | 7 MB |
| clang++ | random_02 |
AC |
790 ms | 8 MB |
| clang++ | small_a_00 |
AC |
679 ms | 7 MB |
| clang++ | small_n_00 |
AC |
24 ms | 4 MB |
| clang++ | small_n_01 |
AC |
77 ms | 5 MB |
| clang++ | small_n_02 |
AC |
63 ms | 5 MB |
| clang++ | small_n_03 |
AC |
43 ms | 4 MB |
| clang++ | small_n_04 |
AC |
24 ms | 4 MB |