Mo
(src/data_structure/mo.hpp)

• View this file on GitHub
• Last update: 2024-11-09 01:34:39+09:00
• Include: #include "src/data_structure/mo.hpp"

Mo

• 配列の要素が不変
• クエリの先読みができる
• 区間クエリ $[l, r)$ の結果から $[l - 1, r), [l + 1, r), [l, r - 1), [l, r + 1)$ の結果を高速に計算できる ( $O(\alpha)$ と仮定)

以上の $3$ つの条件を満たすとき， $Q$ 個のクエリの結果を $O(\alpha N \sqrt{Q} + Q \log Q)$ で計算するデータ構造です． ( $N$ は配列長)

コンストラクタ

Mo mo(int N, int Q)

配列長 $N$ ，クエリ数 $Q$ として初期化します．

計算量

• $O(Q)$

insert

void mo.insert(int l, int r)

区間クエリ $[l, r)$ を追加します．

制約

• $0 \leq l \leq r \leq N$

計算量

• $O(1)$

run

void mo.run(auto add_left, auto add_right, auto delete_left, auto delete_right, auto out)

全クエリの結果を計算します．

add_left は区間クエリ $[l, r)$ の結果から $[l - 1, r)$ の結果を計算する関数です．
add_right は区間クエリ $[l, r)$ の結果から $[l, r + 1)$ の結果を計算する関数です．
delete_left は区間クエリ $[l, r)$ の結果から $[l + 1, r)$ の結果を計算する関数です．
delete_right は区間クエリ $[l, r)$ の結果から $[l, r - 1)$ の結果を計算する関数です．
out は区間を伸縮させた結果を元に，答えを格納する配列に値を書き込む関数です．

main 関数でラムダ式などの形で定義して引数に入れてください．

例えば add_left や out は以下のように定義できます．

auto add_left = [&](int idx) -> void{
    // [idx + 1, r) の結果から [idx, r) の結果を計算する処理を書く
};

auto out = [&](int idx) -> void{
    // 例えば ans[idx] = hoge; など
};

制約

• run が呼び出される前に insert がちょうど $Q$ 回呼び出されている．

計算量

• $O(\alpha N \sqrt{Q} + Q \log Q)$

Depends on

• template (src/template/template.hpp)

Verified with

• verify/library_checker/data_structure/static_range_inversions_query.test.cpp

Code

#pragma once
#include "../template/template.hpp"
struct Mo {
    Mo(const int N, const int Q)
        : n(N), order(Q) {
        width = max<int>(1, 1.0 * N / max<double>(1.0, sqrt(Q * 2.0 / 3.0)));
        iota(order.begin(), order.end(), 0);
    }
    void insert(const int l, const int r) {
        assert(0 <= l and l <= r and r <= n);
        left.emplace_back(l);
        right.emplace_back(r);
    }
    template <typename AL, typename AR, typename DL, typename DR, typename OUT>
    void run(const AL& add_left, const AR& add_right, const DL& delete_left, const DR& delete_right, const OUT& out) {
        assert(left.size() == order.size());
        sort(order.begin(), order.end(), [&](const int i, const int j) {
            const int iblock = left[i] / width, jblock = left[j] / width;
            if(iblock != jblock) return iblock < jblock;
            if(iblock & 1) return right[i] < right[j];
            return right[i] > right[j];
        });
        int nl = 0, nr = 0;
        for(const int 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);
            out(idx);
        }
    }

   private:
    int n, width;
    vector<int> left, right, order;
};

#line 2 "src/template/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<long long, long long>;
#define rep(i, a, b) for(long long i = (a); i < (b); ++i)
#define rrep(i, a, b) for(long long i = (a); i >= (b); --i)
constexpr long long inf = 4e18;
struct SetupIO {
    SetupIO() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout << fixed << setprecision(30);
    }
} setup_io;
#line 3 "src/data_structure/mo.hpp"
struct Mo {
    Mo(const int N, const int Q)
        : n(N), order(Q) {
        width = max<int>(1, 1.0 * N / max<double>(1.0, sqrt(Q * 2.0 / 3.0)));
        iota(order.begin(), order.end(), 0);
    }
    void insert(const int l, const int r) {
        assert(0 <= l and l <= r and r <= n);
        left.emplace_back(l);
        right.emplace_back(r);
    }
    template <typename AL, typename AR, typename DL, typename DR, typename OUT>
    void run(const AL& add_left, const AR& add_right, const DL& delete_left, const DR& delete_right, const OUT& out) {
        assert(left.size() == order.size());
        sort(order.begin(), order.end(), [&](const int i, const int j) {
            const int iblock = left[i] / width, jblock = left[j] / width;
            if(iblock != jblock) return iblock < jblock;
            if(iblock & 1) return right[i] < right[j];
            return right[i] > right[j];
        });
        int nl = 0, nr = 0;
        for(const int 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);
            out(idx);
        }
    }

   private:
    int n, width;
    vector<int> left, right, order;
};

Back to top page