This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub dnx04/algo
#include "misc/mo.hpp"
#pragma once // mo start from 1, so if query is [l, r), then insert [l - 1, r) struct mo_algo { int width; vector<int> left, right, order; mo_algo(int N, int Q) : 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); } } }; /** * @brief Mo's algorithm * @docs docs/misc/mo.md */
#line 2 "misc/mo.hpp" // mo start from 1, so if query is [l, r), then insert [l - 1, r) struct mo_algo { int width; vector<int> left, right, order; mo_algo(int N, int Q) : 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); } } }; /** * @brief Mo's algorithm * @docs docs/misc/mo.md */