XOR of interval
(utilities/xor_of_interval.hpp)

• View this file on GitHub
• Last update: 2023-08-05 00:31:24+09:00
• Include: #include "utilities/xor_of_interval.hpp"
• Link: https://codeforces.com/contest/1849/problem/F

非負整数の半開区間 $[\mathrm{lo}, \mathrm{hi})$ に含まれるそれぞれの整数と $v$ の排他的論理和 (XOR) をとった値の集合はたかだか $O(\log ( \mathrm{hi} - \mathrm{lo}))$ 個の半開区間となる．本関数はその全ての半開区間を列挙する．全ての半開区間の長さは 2 べきである．

使用方法

int lo, hi;

int v;

xor_of_interval(v, lo, hi, [&](int l, int r) {
    // Do something for [l, r).
    // This function is called O(log(hi - lo)) times.
});

問題例

• Educational Codeforces Round 152 (Rated for Div. 2) F. XOR Partition - Codeforces

Code

#pragma once
#include <cassert>

// lo <= (x xor v) < hi なる x の半開区間を列挙
// （lo 以上 hi 未満の各整数 と v の xor をとるとできる O(log(hi - lo)) 個の半開区間を全列挙）
// Verify: https://codeforces.com/contest/1849/problem/F
template <class Int, class F> void xor_of_interval(Int v, Int lo, Int hi, F f) {
    assert(0 <= lo);
    assert(0 <= v);

    for (int d = 0; lo < hi; lo /= 2, hi /= 2, v /= 2, ++d) {
        if (lo & 1) {
            f((lo ^ v) << d, ((lo ^ v) + 1) << d);
            ++lo;
        }
        if (hi & 1) {
            --hi;
            f((hi ^ v) << d, ((hi ^ v) + 1) << d);
        }
    }
}

#line 2 "utilities/xor_of_interval.hpp"
#include <cassert>

// lo <= (x xor v) < hi なる x の半開区間を列挙
// （lo 以上 hi 未満の各整数 と v の xor をとるとできる O(log(hi - lo)) 個の半開区間を全列挙）
// Verify: https://codeforces.com/contest/1849/problem/F
template <class Int, class F> void xor_of_interval(Int v, Int lo, Int hi, F f) {
    assert(0 <= lo);
    assert(0 <= v);

    for (int d = 0; lo < hi; lo /= 2, hi /= 2, v /= 2, ++d) {
        if (lo & 1) {
            f((lo ^ v) << d, ((lo ^ v) + 1) << d);
            ++lo;
        }
        if (hi & 1) {
            --hi;
            f((hi ^ v) << d, ((hi ^ v) + 1) << d);
        }
    }
}

Back to top page