test/yosupo/static_range_sum.test.cpp

View this file on GitHub
Last update: 2023-07-03 22:11:03+09:00
Problem: https://judge.yosupo.jp/problem/static_range_sum

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/static_range_sum"
#include <iostream>

#include "../../sparse_table/disjoint_sparse_table.hpp"
using namespace std;
using llong = long long;

struct Sum {
    using T = llong;
    using value_type = T;

    inline static T operation(T x, T y) {
        return x + y;
    };
};

llong n, q;
vector<llong> a;
DisjointSparseTable<Sum> dst;

int main() {
    cin >> n >> q;
    a.resize(n);
    for (auto &v : a) cin >> v;

    dst.build(a.begin(), a.end());

    while (q--) {
        llong l, r;
        cin >> l >> r;
        cout << dst.fold(l, r) << '\n';
    }
}

#line 1 "test/yosupo/static_range_sum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/static_range_sum"
#include <iostream>

#line 1 "sparse_table/disjoint_sparse_table.hpp"



#include <cassert>
#include <vector>

#line 1 "bit/ctz.hpp"



#include <cstdint>

inline int ctz32_(uint32_t bit) {
    static const int table[] = {
        0,  1, 2,  6,  3,  11, 7,  16, 4,  14, 12, 21, 8,  23, 17, 26,
        31, 5, 10, 15, 13, 20, 22, 25, 30, 9,  19, 24, 29, 18, 28, 27,
    };
    static const uint32_t de_bruijn = 0x04653adf;
    bit &= ~bit + 1;
    return table[(bit * de_bruijn) >> 27];
};
inline int ctz32(uint32_t bit) {
    if (bit == 0) return 32;
#ifdef __has_builtin
    return __builtin_ctz(bit);
#else
    return ctz32_(bit);
#endif
};

inline int ctz64_(uint64_t bit) {
    static const int table[] = {
        0,  1,  2,  7,  3,  13, 8,  19, 4,  25, 14, 28, 9,  34, 20, 40,
        5,  17, 26, 38, 15, 46, 29, 48, 10, 31, 35, 54, 21, 50, 41, 57,
        63, 6,  12, 18, 24, 27, 33, 39, 16, 37, 45, 47, 30, 53, 49, 56,
        62, 11, 23, 32, 36, 44, 52, 55, 61, 22, 43, 51, 60, 42, 59, 58,
    };
    static const uint64_t de_bruijn = 0x0218a392cd3d5dbfull;
    bit &= ~bit + 1;
    return table[(bit * de_bruijn) >> 58];
};
inline int ctz64(uint64_t bit) {
    if (bit == 0) return 64;
#ifdef __has_builtin
    return __builtin_ctzll(bit);
#else
    return ctz64_(bit);
#endif
};


#line 1 "bit/msb.hpp"



#line 5 "bit/msb.hpp"

inline uint32_t msb32_(uint32_t bit) {
    bit |= bit >> 1;
    bit |= bit >> 2;
    bit |= bit >> 4;
    bit |= bit >> 8;
    bit |= bit >> 16;
    return bit ^ (bit >> 1);
};
inline uint32_t msb32(uint32_t x) {
    if (x == 0) return 0;
#ifdef __has_builtin
    return 1u << (31 - __builtin_clz(x));
#else
    return msb32_(x);
#endif
};

inline uint64_t msb64_(uint64_t bit) {
    bit |= bit >> 1;
    bit |= bit >> 2;
    bit |= bit >> 4;
    bit |= bit >> 8;
    bit |= bit >> 16;
    bit |= bit >> 32;
    return bit ^ (bit >> 1);
};
inline uint64_t msb64(uint64_t x) {
    if (x == 0) return 0;
#ifdef __has_builtin
    return 1ull << (63 - __builtin_clzll(x));
#else
    return msb64_(x);
#endif
};


#line 9 "sparse_table/disjoint_sparse_table.hpp"

//===
template <class SemiGroup>
struct DisjointSparseTable {
    using T = typename SemiGroup::value_type;
    using G = SemiGroup;

    std::vector<std::vector<T>> table;

    DisjointSparseTable() = default;
    template <class InputItr>
    DisjointSparseTable(InputItr first, InputItr last) {
        build(first, last);
    };

    template <class InputItr>
    void build(InputItr first, InputItr last) {
        int n = std::distance(first, last);
        int logn = 1;
        while ((1 << logn) < n) logn++;

        table.reserve(logn);
        table.emplace_back(first, last);

        for (int i = 1; i < logn; i++) {
            table.emplace_back(first, last);
            int w = 1 << i;

            for (int k = w; k < n; k += 2 * w) {
                for (int j = k - 2; j >= k - w; j--) {
                    table[i][j] = G::operation(table[i][j], table[i][j + 1]);
                }
                for (int j = k + 1; j < std::min(n, k + w); j++) {
                    table[i][j] = G::operation(table[i][j], table[i][j - 1]);
                }
            }
        }
    };

    // [l, r)
    T fold(int l, int r) {
        assert(l < r);
        assert(l >= 0 && r <= size());
        r--;
        int x = l ^ r;

        if (x == 0)
            return table[0][l];
        else
            return G::operation(table[ctz32(msb32(x))][l],
                                table[ctz32(msb32(x))][r]);
    };

    T fold(int l, int r, SemiGroup e) {
        if (l >= r) return e;
        return fold(l, r);
    };

    int size() {
        return table[0].size();
    };

    const T operator[](int k) {
        return fold(k, k + 1);
    };
};
//===

#line 5 "test/yosupo/static_range_sum.test.cpp"
using namespace std;
using llong = long long;

struct Sum {
    using T = llong;
    using value_type = T;

    inline static T operation(T x, T y) {
        return x + y;
    };
};

llong n, q;
vector<llong> a;
DisjointSparseTable<Sum> dst;

int main() {
    cin >> n >> q;
    a.resize(n);
    for (auto &v : a) cin >> v;

    dst.build(a.begin(), a.end());

    while (q--) {
        llong l, r;
        cin >> l >> r;
        cout << dst.fold(l, r) << '\n';
    }
}