data-structure/utils/sum_count_manager.hpp

View this file on GitHub
Last update: 2025-12-21 17:21:57+09:00
Include: #include "data-structure/utils/sum_count_manager.hpp"

Depends on

Code

#pragma once

#include "../../misc/compress.hpp"
#include "../segtree/segtree.hpp"
#include "../monoid/sum_count.hpp"

template<typename T>
struct SumCountManager {
    Segtree<MonoidSumCount<T, int>> seg;
    Compress<T> comp;

    SumCountManager() = default;
    SumCountManager(vector<T> xs) {
        comp = Compress<T>(xs);
        seg = Segtree<MonoidSumCount<T, int>>((int)comp.size());
    }

    void add(T val) {
        int pos = comp.get(val);
        assert(comp[pos] == val);
        auto x = seg.get(pos);
        seg.set(pos, S(x.sum + val, x.cnt + 1));
    }
};

#line 2 "data-structure/utils/sum_count_manager.hpp"

#line 2 "misc/compress.hpp"

#include <algorithm>
#include <vector>

template <typename T> class Compress {
  public:
    Compress() = default;
    explicit Compress(const std::vector<T> &v) : dat(v) {
        build();
    }
    void push_back(T val) { dat.push_back(val); }
	void build() {
		std::sort(dat.begin(), dat.end());
        dat.erase(std::unique(dat.begin(), dat.end()), dat.end());
	}
    int get(T val) const {
        int pos = std::lower_bound(dat.begin(), dat.end(), val) - dat.begin();
        return pos;
    }
    T operator[](int i) const { return dat[i]; }
    size_t size() const { return dat.size(); }

  private:
    std::vector<T> dat;
};
#line 2 "data-structure/segtree/segtree.hpp"

#include <cassert>
#line 5 "data-structure/segtree/segtree.hpp"

template <class Monoid> class Segtree {
  public:
    using T = typename Monoid::value_type;

    Segtree() : Segtree(0) {}
    explicit Segtree(int n) : Segtree(std::vector<T>(n, Monoid::e())) {}
    explicit Segtree(const std::vector<T> &v) : N((int)v.size()), sz(1) {
        while(sz < N) sz <<= 1;
        node.resize(sz * 2, Monoid::e());
        for(int i = 0; i < N; i++) node[i + sz] = v[i];
        for(int i = sz - 1; i >= 1; i--) {
            node[i] = Monoid::op(node[i << 1], node[i << 1 | 1]);
        }
    }
    void set(int pos, T val) {
        assert(0 <= pos && pos < N);
        pos += sz;
        node[pos] = val;
        while(pos > 1) {
            pos >>= 1;
            node[pos] = Monoid::op(node[pos << 1], node[pos << 1 | 1]);
        }
    }
    T get(int pos) const {
        assert(0 <= pos && pos < N);
        return node[pos + sz];
    }
    void apply(int pos, T val) {
        this->set(pos, Monoid::op(this->get(pos), val));
    }
    T prod(int l, int r) const {
        assert(0 <= l && l <= r && r <= N);
        T value_l = Monoid::e(), value_r = Monoid::e();
        l += sz;
        r += sz;
        while(l < r) {
            if(l & 1) value_l = Monoid::op(value_l, node[l++]);
            if(r & 1) value_r = Monoid::op(node[--r], value_r);
            l >>= 1;
            r >>= 1;
        }
        return Monoid::op(value_l, value_r);
    }
    T all_prod() const { return node[1]; }
    template <class F> int max_right(int l, F f) const {
        assert(0 <= l && l <= N);
        assert(f(Monoid::e()));
        if(l == N) return N;
        l += sz;
        T value_now = Monoid::e();
        do {
            while((l & 1) == 0) l >>= 1;
            if(!f(Monoid::op(value_now, node[l]))) {
                while(l < sz) {
                    l = 2 * l;
                    if(f(Monoid::op(value_now, node[l]))) {
                        value_now = Monoid::op(value_now, node[l]);
                        l++;
                    }
                }
                return (l - sz);
            }
            value_now = Monoid::op(value_now, node[l]);
            l++;
        } while((l & -l) != l);
        return N;
    }
    template <class F> int min_left(int r, F f) const {
        assert(0 <= r && r <= N);
        assert(f(Monoid::e()));
        if(r == 0) return 0;
        r += sz;
        T value_now = Monoid::e();
        do {
            r--;
            while(r > 1 && (r & 1)) r >>= 1;
            if(!f(Monoid::op(node[r], value_now))) {
                while(r < sz) {
                    r = 2 * r + 1;
                    if(f(Monoid::op(node[r], value_now))) {
                        value_now = Monoid::op(node[r], value_now);
                        r--;
                    }
                }
                return ((r + 1) - sz);
            }
            value_now = Monoid::op(node[r], value_now);
        } while((r & -r) != r);
        return 0;
    }

  private:
    int N, sz;
    std::vector<T> node;
};
#line 2 "data-structure/monoid/sum_count.hpp"

template <typename sum_t, typename count_t> struct MonoidSumCount {
    struct S {
        sum_t sum;
        count_t cnt;
        S() = default;
        S(sum_t sum, count_t cnt): sum(sum), cnt(cnt) {}
    };
    using value_type = S;
    inline static S op(const S& l, const S& r) {
        return S(l.sum + r.sum, l.cnt + r.cnt);
    }
    inline static S e() { return S(sum_t(0), count_t(0)); }
};
#line 6 "data-structure/utils/sum_count_manager.hpp"

template<typename T>
struct SumCountManager {
    Segtree<MonoidSumCount<T, int>> seg;
    Compress<T> comp;

    SumCountManager() = default;
    SumCountManager(vector<T> xs) {
        comp = Compress<T>(xs);
        seg = Segtree<MonoidSumCount<T, int>>((int)comp.size());
    }

    void add(T val) {
        int pos = comp.get(val);
        assert(comp[pos] == val);
        auto x = seg.get(pos);
        seg.set(pos, S(x.sum + val, x.cnt + 1));
    }
};