rcpl

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub ruthen71/rcpl

:heavy_check_mark: segment_tree/test/enumerate_segment_tree_nodes.test.cpp

Depends on

Code

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

#include <iostream>

#include "../../segment_tree/enumerate_segment_tree_nodes.hpp"

std::vector<std::pair<long long, long long>> solve(long long l, long long r) {
    const long long n2 = 1LL << 60;
    auto res = enumerate_segment_tree_range_covering_nodes(n2, l, r);
    std::vector<std::pair<long long, long long>> ans;
    for (auto&& i : res) {
        ans.push_back(segment_tree_node_to_range(n2, i));
    }
    return ans;
}

void test1_sample1() {
    long long l = 3, r = 19;
    std::vector<std::pair<long long, long long>> sol = {
        {3, 4}, {4, 8}, {8, 16}, {16, 18}, {18, 19}};
    assert(solve(l, r) == sol);
}
void test2_sample2() {
    long long l = 0, r = 1024;
    std::vector<std::pair<long long, long long>> sol = {{0, 1024}};
    assert(solve(l, r) == sol);
}
void test3_sample3() {
    long long l = 3940649673945088, r = 11549545024454656;
    std::vector<std::pair<long long, long long>> sol = {
        {3940649673945088, 3940649673949184},
        {3940649673949184, 4503599627370496},
        {4503599627370496, 9007199254740992},
        {9007199254740992, 11258999068426240},
        {11258999068426240, 11540474045136896},
        {11540474045136896, 11549270138159104},
        {11549270138159104, 11549545016066048},
        {11549545016066048, 11549545024454656}};
    assert(solve(l, r) == sol);
}

int main() {
    // https://atcoder.jp/contests/abc349/tasks/abc349_d
    test1_sample1();
    test2_sample2();
    test3_sample3();
    int a, b;
    std::cin >> a >> b;
    std::cout << a + b << '\n';
    return 0;
}
#line 1 "segment_tree/test/enumerate_segment_tree_nodes.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"

#include <iostream>

#line 2 "segment_tree/enumerate_segment_tree_nodes.hpp"

#include <algorithm>
#include <cassert>
#include <vector>

#line 2 "misc/topbit.hpp"

#line 2 "misc/countl_zero.hpp"

#if __cplusplus >= 202002L
#include <bit>
#endif

// countl_zero
// (000, 001, 010, 011, 100) -> (32, 31, 30, 30, 29)
#if __cplusplus >= 202002L
using std::countl_zero;
#else
int countl_zero(unsigned int x) {
    return x == 0 ? 32 : __builtin_clz(x);
}
int countl_zero(unsigned long long int x) {
    return x == 0 ? 64 : __builtin_clzll(x);
}
#endif
int countl_zero(int x) { return countl_zero((unsigned int)(x)); }
int countl_zero(long long int x) {
    return countl_zero((unsigned long long int)(x));
}
#line 4 "misc/topbit.hpp"

// topbit
// (000, 001, 010, 011, 100) -> (-1, 0, 1, 1, 2)
int topbit(int x) { return 31 - countl_zero(x); }
int topbit(unsigned int x) { return 31 - countl_zero(x); }
int topbit(long long int x) { return 63 - countl_zero(x); }
int topbit(unsigned long long int x) { return 63 - countl_zero(x); }
#line 8 "segment_tree/enumerate_segment_tree_nodes.hpp"

// 長さ size (2べき) の Segment Tree において区間 [l, r)
// をカバーする区間のノード番号を返す 区間の位置が小さい順に (左から) 返す
template <class T>
std::vector<T> enumerate_segment_tree_range_covering_nodes(const T size,
                                                           T l,
                                                           T r) {
    std::vector<T> ret, ret_rev;
    l += size;
    r += size;
    while (l < r) {
        if (l & 1) ret.push_back(l++);
        if (r & 1) ret_rev.push_back(--r);
        l >>= 1;
        r >>= 1;
    }
    std::reverse(ret_rev.begin(), ret_rev.end());
    ret.insert(ret.end(), ret_rev.begin(), ret_rev.end());
    return ret;
}

// 長さ size (2べき) の Segment Tree において seg[p]
// が含まれる区間のノード番号を返す 区間の幅が小さい順に (下から) 返す
template <class T>
std::vector<T> enumerate_segment_tree_point_containing_nodes(const T size,
                                                             T p) {
    p += size;
    std::vector<T> ret;
    for (int i = 0; (1LL << i) <= size; i++) ret.push_back(p >> i);
    return ret;
}

// 長さ size (2べき) の Segment Tree においてノード番号 i に対応する区間 [l, r)
// を返す https://atcoder.jp/contests/abc349/tasks/abc349_d
// https://atcoder.jp/contests/abc355/tasks/abc355_e
template <class T>
std::pair<T, T> segment_tree_node_to_range(const T size, const T i) {
    assert(size > 0 and i > 0);
    // (1 << n) = size
    const int n = topbit(size);
    // i の最上位ビット
    const int topbiti = topbit(i);
    // [(2 ^ x) * y, (2 ^ x) * (y + 1))
    const int x = n - topbiti;
    const T y = i - (1LL << topbiti);
    return {(1LL << x) * y, (1LL << x) * (y + 1)};
}
#line 6 "segment_tree/test/enumerate_segment_tree_nodes.test.cpp"

std::vector<std::pair<long long, long long>> solve(long long l, long long r) {
    const long long n2 = 1LL << 60;
    auto res = enumerate_segment_tree_range_covering_nodes(n2, l, r);
    std::vector<std::pair<long long, long long>> ans;
    for (auto&& i : res) {
        ans.push_back(segment_tree_node_to_range(n2, i));
    }
    return ans;
}

void test1_sample1() {
    long long l = 3, r = 19;
    std::vector<std::pair<long long, long long>> sol = {
        {3, 4}, {4, 8}, {8, 16}, {16, 18}, {18, 19}};
    assert(solve(l, r) == sol);
}
void test2_sample2() {
    long long l = 0, r = 1024;
    std::vector<std::pair<long long, long long>> sol = {{0, 1024}};
    assert(solve(l, r) == sol);
}
void test3_sample3() {
    long long l = 3940649673945088, r = 11549545024454656;
    std::vector<std::pair<long long, long long>> sol = {
        {3940649673945088, 3940649673949184},
        {3940649673949184, 4503599627370496},
        {4503599627370496, 9007199254740992},
        {9007199254740992, 11258999068426240},
        {11258999068426240, 11540474045136896},
        {11540474045136896, 11549270138159104},
        {11549270138159104, 11549545016066048},
        {11549545016066048, 11549545024454656}};
    assert(solve(l, r) == sol);
}

int main() {
    // https://atcoder.jp/contests/abc349/tasks/abc349_d
    test1_sample1();
    test2_sample2();
    test3_sample3();
    int a, b;
    std::cin >> a >> b;
    std::cout << a + b << '\n';
    return 0;
}
Back to top page