:heavy_check_mark: library/datastructure/GroupWaveletMatrix.hpp

Depends on

Verified with

Code

#pragma once
#include "library/datastructure/FenwickTree.hpp"
#include "library/datastructure/WaveletMatrix.hpp"
#define REP_(i, n) for (int i = 0; i < (n); i++)
template <typename T, group G>
class GroupWaveletMatrix : WaveletMatrix<T, true> {
    using super = WaveletMatrix<T, true>;
    using super::log, super::n, super::nxt, super::comp, super::data,
        super::high_bit, super::mat, super::zero_cnt;
    using U = typename super::U;
    using FT = FenwickTree<G>;
    using S = typename G::value_type;
    std::vector<FT> ft;

  public:
    using super::rank, super::select, super::kth_largest, super::kth_smallest,
        super::range_freq, super::lt, super::leq, super::gt, super::geq;
    GroupWaveletMatrix(std::vector<T> v) : super::WaveletMatrix(v) {
        ft.resize(log);
        for (auto &p : ft)
            p = FT(n);
    }
    GroupWaveletMatrix(std::vector<T> v, const std::vector<S> &w)
        : GroupWaveletMatrix(v) {
        for (int i = 0; i < n; i++)
            add(i, w[i]);
    }
    void add(int idx, const S &val) {
        U a = comp(data[idx]);
        REP_(h, log) {
            idx = nxt(idx, h, a);
            ft[h].add(idx, val);
        }
    }
    S sum(int l, int r, const T &upper) {
        U a = comp(upper);
        S res = G::unit();
        REP_(h, log) {
            if (high_bit(a, h)) {
                int L = mat[h].rank(l, 0), R = mat[h].rank(r, 0);
                G::Rchop(res, ft[h].sum(L, R));
            }
            l = nxt(l, h, a);
            r = nxt(r, h, a);
        }
        return res;
    }
    S sum(int l, int r, const T &lower, const T &upper) {
        return G::op(sum(l, r, upper), G::inverse(sum(l, r, lower)));
    }
    S kth_largest_sum(int l, int r, int k) {
        assert(0 <= k and k < r - l);
        S res = G::unit();
        REP_(h, log) {
            int L = mat[h].rank(l);
            int R = mat[h].rank(r);
            if (R - L > k) {
                l = L + zero_cnt[h];
                r = R + zero_cnt[h];
            } else {
                G::Rchop(res, ft[h].sum(L + zero_cnt[h], R + zero_cnt[h]));
                k -= R - L;
                l -= L;
                r -= R;
            }
        }
        return res;
    }
};
#undef REP_
Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.14.0/x64/lib/python3.14/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.14.0/x64/lib/python3.14/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
    ~~~~~~~~~~~~~~^^^^^^
  File "/opt/hostedtoolcache/Python/3.14.0/x64/lib/python3.14/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
    ~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.14.0/x64/lib/python3.14/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
    ~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.14.0/x64/lib/python3.14/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 312, in update
    raise BundleErrorAt(path, i + 1, "#pragma once found in a non-first line")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: library/algebra/group/Concepts.hpp: line 3: #pragma once found in a non-first line
Back to top page