test/yosupo/ds/point_set_range_frequency.test.cpp

View this file on GitHub
Last update: 2025-09-25 11:45:13+07:00
Problem: https://judge.yosupo.jp/problem/point_set_range_frequency

Depends on

Code

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

#include <bits/stdc++.h>
using namespace std;

#include "ds/ordered_set.hpp"

template<class T> struct PointSetRangeFreq {
    vector<T> a;
    ordered_set<pair<T, int>> s;

    PointSetRangeFreq(const vector<T> &v) : a(v) {
        for (int i = 0; i < a.size(); i++) s.insert({a[i], i});
    }
    void set(int p, T x) {
        s.erase({a[p], p});
        s.insert({a[p] = x, p});
    }
    int freq(int l, int r, T x) {
        return s.order_of({x, r}, false) - s.order_of({x, l}, false);
    }
};

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int &i : a) cin >> i;
    PointSetRangeFreq<int> rf(a);
    while (q--) {
        int op;
        cin >> op;
        if (op == 0) {
            int k, v;
            cin >> k >> v;
            rf.set(k, v);
        } else {
            int l, r, x;
            cin >> l >> r >> x;
            cout << rf.freq(l, r, x) << "\n";
        }
    }
}

#line 1 "test/yosupo/ds/point_set_range_frequency.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/point_set_range_frequency"

#include <bits/stdc++.h>
using namespace std;

#line 2 "ds/ordered_set.hpp"

#line 2 "ds/treap_base.hpp"

#line 2 "ds/bst_base.hpp"

#line 2 "other/st_alloc.hpp"

template<class T> struct st_alloc {
    static inline stack<T> pool;
    void *operator new(size_t) { return pool.emplace(), &pool.top(); }
    void operator delete(void *) {}
};
#line 4 "ds/bst_base.hpp"

namespace bst {
    template<class T> struct node : st_alloc<T> {
        T *l = nullptr, *r = nullptr;
        void pull() { ((T *)this)->_pull(); }
    };
} // namespace bst
#line 4 "ds/treap_base.hpp"

namespace treap {
    template<class T> using key_t = decltype(declval<T>().key);
    template<class T> struct node : bst::node<T> {
        uint64_t pr = rng();

        static uint64_t rng() {
            static mt19937_64 mt(
                chrono::steady_clock::now().time_since_epoch().count());
            return mt();
        }
    };

    template<class T> T *merge(node<T> *_l, node<T> *_r) {
        T *l = (T *)_l, *r = (T *)_r;
        if (!l || !r) return l ? l : r;
        if (l->pr > r->pr) {
            l->r = merge(l->r, r), l->pull();
            return l;
        } else {
            r->l = merge(l, r->l), r->pull();
            return r;
        }
    }
    template<class T>
    pair<T *, T *> split(node<T> *_t, const key_t<T> &k, bool include = true) {
        T *t = (T *)_t;
        if (!t) return {nullptr, nullptr};
        if (k < t->key || (k == t->key && !include)) {
            auto s = split(t->l, k, include);
            t->l = s.second, t->pull();
            return {s.first, t};
        } else {
            auto s = split(t->r, k, include);
            t->r = s.first, t->pull();
            return {t, s.second};
        }
    }
} // namespace treap
#line 4 "ds/ordered_set.hpp"

// NOTE: The copy constructor only copies the pointer. Be careful when doing
// `ordered_set<> s2 = s1;`
namespace oset {
    using treap::merge, treap::split;
    template<class T> struct ordered_set {
        ordered_set() {}

        void insert(const T &k) {
            if (contains(k)) return;
            auto [a, b] = split(root, k, false);
            root = merge(a, merge(new node(k), b));
        }
        void erase(const T &k) {
            if (!contains(k)) return;
            node *a, *b, *c;
            tie(a, b) = split(root, k, false);
            tie(b, c) = split(b, k, true);
            root = merge(a, c);
        }
        optional<T> kth_order(int k) const {
            if (empty() || k > size()) return nullopt;
            int ord = 0;
            for (auto t = root; t;) {
                int w = ord + size(t->l) + 1;
                if (w == k) return t->key;
                t = k < w ? t->l : (ord = w, t->r);
            };
            return nullopt;
        }
        int order_of(const T &k, bool include = true) const {
            if (empty()) return 0;
            int ord = 0;
            for (auto t = root; t;) {
                if (k < t->key || (k == t->key && !include)) {
                    t = t->l;
                } else {
                    ord += size(t->l) + 1, t = t->r;
                }
            }
            return ord;
        }
        optional<T> pre_upper_bound(const T &k) const {
            return kth_order(order_of(k));
        }
        optional<T> lower_bound(const T &k) const {
            return kth_order(order_of(k, false) + 1);
        }

        int size() const { return size(root); }
        bool empty() const { return size() == 0; }
        bool contains(const T &k) const {
            for (auto t = root; t; t = k < t->key ? t->l : t->r)
                if (k == t->key) return true;
            return false;
        }

      private:
        struct node : treap::node<node> {
            using base = treap::node<node>;
            using base::l, base::r;

            T key;
            int sz = 1;
            node() {}
            node(const T k) : key(k) {}
            void _pull() { sz = size(l) + 1 + size(r); }
        };
        node *root = nullptr;
        static int size(node *t) { return t ? t->sz : 0; }
    };
} // namespace oset
using oset::ordered_set;
#line 7 "test/yosupo/ds/point_set_range_frequency.test.cpp"

template<class T> struct PointSetRangeFreq {
    vector<T> a;
    ordered_set<pair<T, int>> s;

    PointSetRangeFreq(const vector<T> &v) : a(v) {
        for (int i = 0; i < a.size(); i++) s.insert({a[i], i});
    }
    void set(int p, T x) {
        s.erase({a[p], p});
        s.insert({a[p] = x, p});
    }
    int freq(int l, int r, T x) {
        return s.order_of({x, r}, false) - s.order_of({x, l}, false);
    }
};

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int &i : a) cin >> i;
    PointSetRangeFreq<int> rf(a);
    while (q--) {
        int op;
        cin >> op;
        if (op == 0) {
            int k, v;
            cin >> k >> v;
            rf.set(k, v);
        } else {
            int l, r, x;
            cin >> l >> r >> x;
            cout << rf.freq(l, r, x) << "\n";
        }
    }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	5 ms	4 MB
g++	many_query_0_00	AC	426 ms	21 MB
g++	many_query_0_01	AC	571 ms	21 MB
g++	many_query_0_02	AC	612 ms	21 MB
g++	many_query_0_03	AC	627 ms	21 MB
g++	many_query_1_00	AC	248 ms	13 MB
g++	many_query_1_01	AC	316 ms	13 MB
g++	many_query_1_02	AC	323 ms	13 MB
g++	many_query_1_03	AC	312 ms	13 MB
g++	max_00	AC	302 ms	17 MB
g++	max_01	AC	329 ms	17 MB
g++	max_02	AC	387 ms	17 MB
g++	max_03	AC	437 ms	17 MB
g++	max_04	AC	474 ms	17 MB
g++	max_05	AC	444 ms	17 MB
g++	max_06	AC	442 ms	17 MB
g++	max_07	AC	447 ms	17 MB
g++	medium_00	AC	112 ms	8 MB
g++	medium_01	AC	108 ms	8 MB
g++	medium_02	AC	107 ms	8 MB
g++	medium_03	AC	111 ms	7 MB
g++	medium_04	AC	113 ms	8 MB
g++	small_n_00	AC	48 ms	4 MB
g++	small_n_01	AC	48 ms	8 MB
g++	small_n_02	AC	51 ms	8 MB
clang++	example_00	AC	5 ms	4 MB
clang++	many_query_0_00	AC	429 ms	21 MB
clang++	many_query_0_01	AC	565 ms	21 MB
clang++	many_query_0_02	AC	614 ms	21 MB
clang++	many_query_0_03	AC	571 ms	21 MB
clang++	many_query_1_00	AC	251 ms	13 MB
clang++	many_query_1_01	AC	310 ms	13 MB
clang++	many_query_1_02	AC	339 ms	13 MB
clang++	many_query_1_03	AC	304 ms	13 MB
clang++	max_00	AC	294 ms	17 MB
clang++	max_01	AC	348 ms	17 MB
clang++	max_02	AC	370 ms	17 MB
clang++	max_03	AC	428 ms	17 MB
clang++	max_04	AC	487 ms	17 MB
clang++	max_05	AC	456 ms	17 MB
clang++	max_06	AC	474 ms	17 MB
clang++	max_07	AC	460 ms	17 MB
clang++	medium_00	AC	115 ms	8 MB
clang++	medium_01	AC	111 ms	8 MB
clang++	medium_02	AC	110 ms	8 MB
clang++	medium_03	AC	113 ms	7 MB
clang++	medium_04	AC	116 ms	8 MB
clang++	small_n_00	AC	48 ms	4 MB
clang++	small_n_01	AC	48 ms	8 MB
clang++	small_n_02	AC	52 ms	8 MB