Test/LC/static_range_frequency.test.cpp

View this file on GitHub
Last update: 2025-04-14 13:20:45+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 "../../Src/Template/IOSetting.hpp"
#include "../../Src/DataStructure/Mo/Mo.hpp"
#include "../../Src/Sequence/CompressedSequence.hpp"

#include <iostream>
#include <vector>

using namespace zawa;

int N, Q, X[500050];
struct query {
    usize l, r;
};
int main() {
    SetFastIO();

    std::cin >> N >> Q;
    std::vector<int> A(N);
    for (int& a : A) std::cin >> a;
    CompressedSequence comp{A};
    std::vector<query> q(Q);
    for (int i{} ; auto& [l, r] : q) {
        std::cin >> l >> r >> X[i];
        i++;
    }
    std::vector<int> cnt(comp.size());
    auto add{[&](int i) -> void {
        cnt[comp.map(i)]++;
    }};
    auto del{[&](int i) -> void {
        cnt[comp.map(i)]--;
    }};
    auto eval{[&](int i) -> int {
        auto j = comp.find(X[i]);
        if (j == decltype(comp)::NotFound) return 0;
        else return cnt[j];
    }};
    for (int ans : Mo(q, add, add, del, del, eval)) std::cout << ans << '\n';
}

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

#line 2 "Src/Template/IOSetting.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 4 "Src/Template/IOSetting.hpp"

#include <iostream>
#include <iomanip>

namespace zawa {

void SetFastIO() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
}

void SetPrecision(u32 dig) {
    std::cout << std::fixed << std::setprecision(dig);
}

} // namespace zawa
#line 2 "Src/DataStructure/Mo/Mo.hpp"

#line 4 "Src/DataStructure/Mo/Mo.hpp"

#include <algorithm>
#include <bit>
#include <cassert>
#include <vector>
#include <type_traits>

namespace zawa {

namespace internal {

// reference: https://codeforces.com/blog/entry/61203?#comment-1064868
u64 hilbertOrder(u64 x, u64 y, usize dim) {
    const u64 max{(1ull << dim) - 1};
    assert(x <= max);
    assert(y <= max);
    u64 res{};
    for (u64 s{1ull << (dim - 1)} ; s ; s >>= 1) {
        bool rx{static_cast<bool>(x & s)}, ry{static_cast<bool>(y & s)};
        res = (res << 2) | (rx ? ry ? 2 : 1 : ry ? 3 : 0);
        if (!rx) {
            if (ry) x ^= max, y ^= max;
            std::swap(x, y);
        }
    }
    return res;
}

} // namespace internal

template <class T, class AddL, class AddR, class DelL, class DelR, class Eval>
std::vector<typename std::invoke_result_t<Eval, usize>> Mo(std::vector<T> qs, AddL addL, AddR addR, DelL delL, DelR delR, Eval eval, bool reset = false) {
    usize log{};
    for (const T& lr : qs) log = std::max<usize>(log, std::bit_width(lr.r));
    std::vector<std::pair<T, usize>> ord(qs.size());
    std::vector<u64> h(qs.size());
    for (usize i{} ; i < qs.size() ; i++) {
        ord[i] = {qs[i], i};
        h[i] = internal::hilbertOrder(qs[i].l, qs[i].r, log);
    }
    std::sort(ord.begin(), ord.end(), [&](const auto& L, const auto& R) -> bool {
            return h[L.second] < h[R.second];
            });
    std::vector<typename std::invoke_result_t<Eval, usize>> res(qs.size());
    usize L{}, R{};
    for (const auto& [lr, id] : ord) {
        while (R < lr.r) addR(R++);
        while (L > lr.l) addL(--L);
        while (R > lr.r) delR(--R);
        while (L < lr.l) delL(L++);
        res[id] = eval(id);
    }
    if (reset) while (R > L) delR(--R);
    return res;
}

} // namespace zawa
#line 2 "Src/Sequence/CompressedSequence.hpp"

#line 4 "Src/Sequence/CompressedSequence.hpp"

#line 8 "Src/Sequence/CompressedSequence.hpp"
#include <iterator>
#include <limits>

namespace zawa {

template <class T>
class CompressedSequence {
public:

    static constexpr u32 NotFound = std::numeric_limits<u32>::max();

    CompressedSequence() = default;

    template <class InputIterator>
    CompressedSequence(InputIterator first, InputIterator last) : comped_(first, last), f_{} {
        std::sort(comped_.begin(), comped_.end());
        comped_.erase(std::unique(comped_.begin(), comped_.end()), comped_.end());
        comped_.shrink_to_fit();
        f_.reserve(std::distance(first, last));
        for (auto it{first} ; it != last ; it++) {
            f_.emplace_back(std::distance(comped_.begin(), std::lower_bound(comped_.begin(), comped_.end(), *it)));
        }
    }

    CompressedSequence(const std::vector<T>& A) : CompressedSequence(A.begin(), A.end()) {}

    inline usize size() const noexcept {
        return comped_.size();
    }

    u32 operator[](const T& v) const {
        return std::distance(comped_.begin(), std::lower_bound(comped_.begin(), comped_.end(), v));
    }

    u32 upper_bound(const T& v) const {
        return std::distance(comped_.begin(), std::upper_bound(comped_.begin(), comped_.end(), v));
    }

    u32 find(const T& v) const {
        u32 i = std::distance(comped_.begin(), std::lower_bound(comped_.begin(), comped_.end(), v));
        return i == comped_.size() or comped_[i] != v ? NotFound : i;
    }

    bool contains(const T& v) const {
        u32 i = std::distance(comped_.begin(), std::lower_bound(comped_.begin(), comped_.end(), v));
        return i < comped_.size() and comped_[i] == v;
    }

    u32 at(const T& v) const {
        u32 res = find(v);
        assert(res != NotFound);
        return res;
    }

    inline u32 map(u32 i) const noexcept {
        assert(i < f_.size());
        return f_[i];
    }

    inline T inverse(u32 i) const noexcept {
        assert(i < size());
        return comped_[i];
    }

    inline std::vector<T> comped() const noexcept {
        return comped_;
    }

private:

    std::vector<T> comped_;

    std::vector<u32> f_;

};

} // namespace zawa
#line 6 "Test/LC/static_range_frequency.test.cpp"

#line 9 "Test/LC/static_range_frequency.test.cpp"

using namespace zawa;

int N, Q, X[500050];
struct query {
    usize l, r;
};
int main() {
    SetFastIO();

    std::cin >> N >> Q;
    std::vector<int> A(N);
    for (int& a : A) std::cin >> a;
    CompressedSequence comp{A};
    std::vector<query> q(Q);
    for (int i{} ; auto& [l, r] : q) {
        std::cin >> l >> r >> X[i];
        i++;
    }
    std::vector<int> cnt(comp.size());
    auto add{[&](int i) -> void {
        cnt[comp.map(i)]++;
    }};
    auto del{[&](int i) -> void {
        cnt[comp.map(i)]--;
    }};
    auto eval{[&](int i) -> int {
        auto j = comp.find(X[i]);
        if (j == decltype(comp)::NotFound) return 0;
        else return cnt[j];
    }};
    for (int ans : Mo(q, add, add, del, del, eval)) std::cout << ans << '\n';
}