test/mo/hilbert_mo_static_range_frequency.test.cpp

View this file on GitHub
Last update: 2026-02-28 01:07:59+09:00
Problem: https://judge.yosupo.jp/problem/static_range_frequency

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/static_range_frequency"

#include "mo/hilbert_mo.hpp"
#include "mo/sqrt_freq_table.hpp"
#include <bits/stdc++.h>

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    int N, Q;
    std::cin >> N >> Q;
    std::vector<int> A(N);
    for (auto &a : A) {
        std::cin >> a;
    }
    auto C = A;
    std::ranges::sort(C);
    C.erase(unique(C.begin(), C.end()), C.end());
    for (auto &a : A) {
        auto it = std::ranges::lower_bound(C, a);
        a = int(it - C.begin());
    }
    std::vector<int> X(Q);
    HilbertMo mo(N);
    for (auto &x : X) {
        int l, r;
        std::cin >> l >> r >> x;
        auto it = std::ranges::lower_bound(C, x);
        x = (it != C.end() && *it == x) ? int(it - C.begin()) : -1;
        mo.add(l, r);
    }
    SqrtFreqTable table(int(C.size()) - 1);
    std::vector<int> ans(Q);
    auto add = [&](int i) { table.insert(A[i]); };
    auto remove = [&](int i) { table.erase(A[i]); };
    auto eval = [&](int i) { ans[i] = (X[i] == -1) ? 0 : table.count(X[i]); };
    mo.solve(add, remove, eval);
    std::ranges::copy(ans, std::ostream_iterator<int>(std::cout, "\n"));
}

#line 1 "test/mo/hilbert_mo_static_range_frequency.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/static_range_frequency"

#line 1 "mo/hilbert_mo.hpp"



#include <algorithm>
#include <array>
#include <cassert>
#include <vector>

struct HilbertMo {
    HilbertMo(int n) : n_(n), log_(std::bit_width(unsigned(n))) {}
    void add(int l, int r) {
        assert(0 <= l && l <= r && r <= n_);
        auto index = int(queries_.size());
        auto order = hilbert_order(l, r);
        queries_.push_back({l, r, index, order});
    }
    void solve(auto add, auto remove, auto eval) { solve(add, add, remove, remove, eval); }
    void solve(auto add_left, auto add_right, auto remove_left, auto remove_right, auto eval) {
        sort(queries_.begin(), queries_.end());
        auto l = 0, r = 0;
        for (auto [left, right, index, order] : queries_) {
            while (left < l) {
                add_left(--l);
            }
            while (r < right) {
                add_right(r++);
            }
            while (l < left) {
                remove_left(l++);
            }
            while (right < r) {
                remove_right(--r);
            }
            eval(index);
        }
    }

private:
    struct query {
        int left, right, index;
        long long order;
        bool operator<(const query &other) const { return order < other.order; }
    };
    long long hilbert_order(int x, int y) const {
        auto d = 0LL;
        for (auto s = 1 << log_; s > 0; s >>= 1) {
            bool rx = x & s, ry = y & s;
            d = (d << 2) | ((rx * 3) ^ ry);
            if (!ry) {
                if (rx) {
                    x = ~x;
                    y = ~y;
                }
                std::swap(x, y);
            }
        }
        return d;
    }
    std::vector<query> queries_;
    const int n_, log_;
};


#line 1 "mo/sqrt_freq_table.hpp"



#line 6 "mo/sqrt_freq_table.hpp"
#include <cmath>
#line 8 "mo/sqrt_freq_table.hpp"

struct SqrtFreqTable {
    explicit SqrtFreqTable(int max_val)
        : m_(std::max(1, max_val)), b_sz_(int(std::sqrt(m_))), freq_(m_ + 1),
          bucket_(m_ / b_sz_ + 1) {}
    void insert(int x) { // O(1)
        assert(0 <= x && x <= m_);
        ++freq_[x];
        ++bucket_[x / b_sz_];
        ++total_;
        distinct_ += int(freq_[x] == 1);
    }
    void erase(int x) { // O(1)
        assert(0 <= x && x <= m_);
        assert(0 < freq_[x]);
        --freq_[x];
        --bucket_[x / b_sz_];
        --total_;
        distinct_ -= int(freq_[x] == 0);
    }
    int count(int x) const { // O(1)
        assert(0 <= x && x <= m_);
        return freq_[x];
    }
    int size() const { return total_; }
    int count_distinct() const { return distinct_; }
    int kth(int k) const { // O(sqrt(M)), 0-indexed
        auto cnt = 0;
        for (auto i = 0; i < m_ / b_sz_ + 1; ++i) {
            if (cnt + bucket_[i] <= k) {
                cnt += bucket_[i];
                continue;
            }
            auto x = i * b_sz_;
            while ((cnt += freq_[x]) <= k) {
                ++x;
            }
            return x;
        }
        return -1;
    };
    int rank(int x) const { // O(sqrt(M)), count y s.t. y < x
        if (x < 0) {
            return 0;
        }
        if (m_ < x) {
            return total_;
        }
        auto cnt = 0;
        for (auto i = 0; i < x / b_sz_; ++i) {
            cnt += bucket_[i];
        }
        for (auto i = x / b_sz_ * b_sz_; i < x; ++i) {
            cnt += freq_[i];
        }
        return cnt;
    }

private:
    const int m_, b_sz_;
    std::vector<int> freq_, bucket_;
    int total_ = 0, distinct_ = 0;
};


#line 5 "test/mo/hilbert_mo_static_range_frequency.test.cpp"
#include <bits/stdc++.h>

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    int N, Q;
    std::cin >> N >> Q;
    std::vector<int> A(N);
    for (auto &a : A) {
        std::cin >> a;
    }
    auto C = A;
    std::ranges::sort(C);
    C.erase(unique(C.begin(), C.end()), C.end());
    for (auto &a : A) {
        auto it = std::ranges::lower_bound(C, a);
        a = int(it - C.begin());
    }
    std::vector<int> X(Q);
    HilbertMo mo(N);
    for (auto &x : X) {
        int l, r;
        std::cin >> l >> r >> x;
        auto it = std::ranges::lower_bound(C, x);
        x = (it != C.end() && *it == x) ? int(it - C.begin()) : -1;
        mo.add(l, r);
    }
    SqrtFreqTable table(int(C.size()) - 1);
    std::vector<int> ans(Q);
    auto add = [&](int i) { table.insert(A[i]); };
    auto remove = [&](int i) { table.erase(A[i]); };
    auto eval = [&](int i) { ans[i] = (X[i] == -1) ? 0 : table.count(X[i]); };
    mo.solve(add, remove, eval);
    std::ranges::copy(ans, std::ostream_iterator<int>(std::cout, "\n"));
}