bit/subset_range_add_point_get.hpp

• View this file on GitHub
• Last update: 2026-07-08 16:34:34+09:00
• Include: #include "bit/subset_range_add_point_get.hpp"

Depends on

• template/random.hpp

Verified with

• bit/test/subset_range_add_point_get.test.cpp

Code

#pragma once
#include <cassert>
#include <utility>
#include <vector>
#include "../template/random.hpp"
template <typename T>
class SubsetRangeAddPointGet {
    unsigned l, ty0, ty1, ty2;
    std::vector<T> arr;

    static long long eval(unsigned ty0, unsigned ty1, unsigned ty2,
                          const std::vector<std::pair<unsigned, unsigned>> &add,
                          const std::vector<unsigned> &get) {
        long long cost = 0;
        for (auto [low, high] : add) {
            unsigned tot = ty0 & (low ^ high);
            tot |= ty1 & low;
            tot |= ty2 & high;
            cost += 1LL << __builtin_popcount(tot);
        }
        for (unsigned idx : get) {
            unsigned tot = (ty1 & ~idx) | (ty2 & idx);
            cost += 1LL << __builtin_popcount(tot);
        }
        return cost;
    }

public:
    SubsetRangeAddPointGet(unsigned l) : l(l), ty0(0), ty1(0), ty2(0), arr(1 << l, T()) {
        for (unsigned i = 0; i < l; ++i) {
            int t = uniform(3);
            (t == 0 ? ty0 : (t == 1 ? ty1 : ty2)) += 1u << i;
        }
    }
    void read_queries(const std::vector<std::pair<unsigned, unsigned>> &add,
                      const std::vector<unsigned> &get) {
        ty0 = ty1 = ty2 = 0;
        for (unsigned i = 0; i < l; ++i) {
            unsigned c0 = eval(ty0 | (1u << i), ty1, ty2, add, get);
            unsigned c1 = eval(ty0, ty1 | (1u << i), ty2, add, get);
            unsigned c2 = eval(ty0, ty1, ty2 | (1u << i), add, get);
            unsigned c = std::min({c0, c1, c2});
            (c0 == c ? ty0 : (c1 == c ? ty1 : ty2)) |= 1u << i;
        }
    }
    void add(unsigned low, unsigned high, T v) {
        assert((low | high) == high);
        assert(high < (1u << l));
        unsigned tot = ty0 & (low ^ high);
        tot |= ty1 & low;
        tot |= ty2 & ~high;
        unsigned base = ty0 & low;
        base |= ty1 & (low ^ high);
        base |= ty2 & low;
        unsigned q = (ty1 & low) | (ty2 & ~high);
        T mv = -v;
        if (__builtin_parity(ty1 & low)) {
            std::swap(v, mv);
        }
        for (unsigned st = tot; st; st = (st - 1) & tot) {
            arr[base | st] += (__builtin_parity(q & st) ? mv : v);
        }
        arr[base] += v;
    }
    T get(unsigned idx) const {
        assert(idx < (1u << l));
        unsigned tot = (ty1 & ~idx) | (ty2 & idx);
        unsigned base = (ty0 | ty1) & idx;
        T ans = arr[base];
        for (unsigned st = tot; st; st = (st - 1) & tot) {
            ans += arr[base | st];
        }
        return ans;
    }
};

#line 2 "bit/subset_range_add_point_get.hpp"
#include <cassert>
#include <utility>
#include <vector>
#line 2 "template/random.hpp"
#include <chrono>
#include <random>

#if defined(LOCAL) || defined(FIX_SEED)
std::mt19937_64 mt(123456789);
#else
std::mt19937_64 mt(std::chrono::steady_clock::now().time_since_epoch().count());
#endif

template <typename T>
T uniform(T l, T r) {
    return std::uniform_int_distribution<T>(l, r - 1)(mt);
}
template <typename T>
T uniform(T n) {
    return std::uniform_int_distribution<T>(0, n - 1)(mt);
}
#line 6 "bit/subset_range_add_point_get.hpp"
template <typename T>
class SubsetRangeAddPointGet {
    unsigned l, ty0, ty1, ty2;
    std::vector<T> arr;

    static long long eval(unsigned ty0, unsigned ty1, unsigned ty2,
                          const std::vector<std::pair<unsigned, unsigned>> &add,
                          const std::vector<unsigned> &get) {
        long long cost = 0;
        for (auto [low, high] : add) {
            unsigned tot = ty0 & (low ^ high);
            tot |= ty1 & low;
            tot |= ty2 & high;
            cost += 1LL << __builtin_popcount(tot);
        }
        for (unsigned idx : get) {
            unsigned tot = (ty1 & ~idx) | (ty2 & idx);
            cost += 1LL << __builtin_popcount(tot);
        }
        return cost;
    }

public:
    SubsetRangeAddPointGet(unsigned l) : l(l), ty0(0), ty1(0), ty2(0), arr(1 << l, T()) {
        for (unsigned i = 0; i < l; ++i) {
            int t = uniform(3);
            (t == 0 ? ty0 : (t == 1 ? ty1 : ty2)) += 1u << i;
        }
    }
    void read_queries(const std::vector<std::pair<unsigned, unsigned>> &add,
                      const std::vector<unsigned> &get) {
        ty0 = ty1 = ty2 = 0;
        for (unsigned i = 0; i < l; ++i) {
            unsigned c0 = eval(ty0 | (1u << i), ty1, ty2, add, get);
            unsigned c1 = eval(ty0, ty1 | (1u << i), ty2, add, get);
            unsigned c2 = eval(ty0, ty1, ty2 | (1u << i), add, get);
            unsigned c = std::min({c0, c1, c2});
            (c0 == c ? ty0 : (c1 == c ? ty1 : ty2)) |= 1u << i;
        }
    }
    void add(unsigned low, unsigned high, T v) {
        assert((low | high) == high);
        assert(high < (1u << l));
        unsigned tot = ty0 & (low ^ high);
        tot |= ty1 & low;
        tot |= ty2 & ~high;
        unsigned base = ty0 & low;
        base |= ty1 & (low ^ high);
        base |= ty2 & low;
        unsigned q = (ty1 & low) | (ty2 & ~high);
        T mv = -v;
        if (__builtin_parity(ty1 & low)) {
            std::swap(v, mv);
        }
        for (unsigned st = tot; st; st = (st - 1) & tot) {
            arr[base | st] += (__builtin_parity(q & st) ? mv : v);
        }
        arr[base] += v;
    }
    T get(unsigned idx) const {
        assert(idx < (1u << l));
        unsigned tot = (ty1 & ~idx) | (ty2 & idx);
        unsigned base = (ty0 | ty1) & idx;
        T ans = arr[base];
        for (unsigned st = tot; st; st = (st - 1) & tot) {
            ans += arr[base | st];
        }
        return ans;
    }
};

Back to top page