Submission #73651999

---

Source Code Expand

#include <bits/stdc++.h>

#ifdef LOCAL
#include <library/my_library/utility/debug.hpp>
#else
#define debug(...)
#endif

using namespace std;
namespace rv = std::views;  // NOLINT

// clang-format off
using lint = long long;
#define ALL(a) (a).begin(), (a).end()

template <class T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
template <class T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
inline void Yes(bool b = true) { println("{}",(b ? "Yes" : "No")); }
inline void No() { println("{}", "No");}
// clang-format on

#include <algorithm>
#include <cmath>
#include <functional>
#include <numeric>
#include <vector>

/**
 * @brief Mo's Algorithm (平方分割によるオフラインクエリ処理)
 * 使い方:
 *  Mo mo(N);
 *  mo.add_query(l, r);
 *  mo.solve(add_l, add_r, rem_l, rem_r, get_ans);
 */
struct Mo {
    int n;                                     // 配列のサイズ
    int block_size;                            // ブロックサイズ (√N)
    std::vector<std::pair<int, int>> queries;  // クエリ (l, r)
    std::vector<int> order;                    // クエリの処理順序

    /**
     * @brief コンストラクタ
     * @param n 配列のサイズ
     */
    Mo(int n) : n(n), block_size(std::sqrt(n) + 1) {}

    /**
     * @brief クエリを追加
     * @param l 区間の左端 (0-indexed)
     * @param r 区間の右端 (0-indexed, 半開区間 [l, r))
     */
    void add_query(int l, int r) { queries.emplace_back(l, r); }

    /**
     * @brief クエリを最適な順序でソート
     * @note 左端のブロック番号でソート、同じブロックなら右端でソート
     *       奇数ブロックは右端を降順にすることで移動回数を削減
     */
    void build() {
        int q = queries.size();
        order.resize(q);
        std::iota(order.begin(), order.end(), 0);

        std::sort(order.begin(), order.end(), [&](int i, int j) {
            int block_i = queries[i].first / block_size;
            int block_j = queries[j].first / block_size;

            if (block_i != block_j) return block_i < block_j;

            // 奇数ブロックは右端を降順にする (Hilbert曲線の近似)
            if (block_i & 1) return queries[i].second > queries[j].second;
            return queries[i].second < queries[j].second;
        });
    }

    /**
     * @brief クエリを処理して結果を返す
     *
     * @tparam AddLeft 左端を追加する関数 (int idx) -> void
     * @tparam AddRight 右端を追加する関数 (int idx) -> void
     * @tparam RemoveLeft 左端を削除する関数 (int idx) -> void
     * @tparam RemoveRight 右端を削除する関数 (int idx) -> void
     * @tparam GetAnswer 現在の状態から答えを取得する関数 () -> T
     *
     * @return クエリの答えの配列 (元のクエリの順序)
     */
    template <typename AddLeft, typename AddRight, typename RemoveLeft, typename RemoveRight, typename GetAnswer>
    auto solve(AddLeft add_left, AddRight add_right, RemoveLeft remove_left, RemoveRight remove_right,
               GetAnswer get_answer) {
        using Answer = decltype(get_answer());
        int q = queries.size();
        std::vector<Answer> answers(q);

        build();

        int current_l = 0, current_r = 0;

        for (int idx : order) {
            auto [l, r] = queries[idx];

            // 左端を拡張
            while (current_l > l) {
                current_l--;
                add_left(current_l);
            }

            // 右端を拡張
            while (current_r < r) {
                add_right(current_r);
                current_r++;
            }

            // 左端を縮小
            while (current_l < l) {
                remove_left(current_l);
                current_l++;
            }

            // 右端を縮小
            while (current_r > r) {
                current_r--;
                remove_right(current_r);
            }

            answers[idx] = get_answer();
        }

        return answers;
    }

    /**
     * @brief クエリを処理して結果を返す (簡易版)
     * @note add/remove が左右で同じ処理の場合に使用
     *
     * @tparam Add 要素を追加する関数 (int idx) -> void
     * @tparam Remove 要素を削除する関数 (int idx) -> void
     * @tparam GetAnswer 現在の状態から答えを取得する関数 () -> T
     *
     * @return クエリの答えの配列 (元のクエリの順序)
     */
    template <typename Add, typename Remove, typename GetAnswer>
    auto solve(Add add, Remove remove, GetAnswer get_answer) {
        return solve(add, add, remove, remove, get_answer);
    }
};

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int N, Q;
    cin >> N >> Q;
    Mo mo(N);
    vector<int> A(N);
    for (auto&& a : A) cin >> a;
    for (int i = 0; i < Q; i++) {
        int l, r;
        cin >> l >> r;
        l--;
        mo.add_query(l, r);
    }
    mo.build();
    unordered_map<int, int> mp;
    auto add = [&](int r) { mp[A[r]]++; };
    auto remove = [&](int l) {
        mp[A[l]]--;
        if (mp[A[l]] == 0) mp.erase(A[l]);
    };
    auto get_ans = [&] { return ssize(mp); };
    auto ans = mo.solve(add, add, remove, remove, get_ans);
    for (int i = 0; i < ssize(ans); i++) {
        cout << ans[i] << '\n';
    }
}

Submission Info

Judge Result