結果

問題 No.3205 Range Pairwise Xor Query
コンテスト
ユーザー elphe
提出日時 2025-07-20 09:31:38
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 150 ms / 2,000 ms
コード長 1,543 bytes
コンパイル時間 1,065 ms
コンパイル使用メモリ 90,120 KB
実行使用メモリ 50,160 KB
最終ジャッジ日時 2025-07-20 09:31:46
合計ジャッジ時間 6,130 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <cstdint>
#include <array>
#include <vector>

static inline constexpr std::vector<std::array<uint_fast32_t, 26>> prepare(const uint_fast32_t N, const std::vector<uint_fast32_t>& A) noexcept
{
	std::vector<std::array<uint_fast32_t, 26>> csum_count(N + 1);
	for (uint_fast32_t i = 0; i != N; ++i)
		for (uint_fast32_t j = 0; j != 26; ++j)
			csum_count[i + 1][j] = csum_count[i][j] + ((A[i] >> j) & 1);

	return csum_count;
}

static inline constexpr std::vector<uint_fast64_t> solve(const uint_fast32_t Q, const std::vector<uint_fast32_t>& L, const std::vector<uint_fast32_t>& R, const std::vector<std::array<uint_fast32_t, 26>>& csum_count) noexcept
{
	std::vector<uint_fast64_t> ans(Q, 0);
	for (uint_fast32_t i = 0; i != Q; ++i)
		for (uint_fast32_t j = 0; j != 26; ++j)
		{
			const uint_fast32_t count[2] = { (R[i] + 1 - L[i]) - (csum_count[R[i]][j] - csum_count[L[i] - 1][j]), csum_count[R[i]][j] - csum_count[L[i] - 1][j] };
			ans[i] += (static_cast<uint_fast64_t>(count[0]) * count[1]) << j;
		}

	return ans;
}

static inline void output(const uint_fast32_t Q, const std::vector<uint_fast64_t>& ans) noexcept
{
	for (uint_fast32_t i = 0; i != Q; ++i)
		std::cout << ans[i] << '\n';
}

int main()
{
	std::cin.tie(nullptr);
	std::ios::sync_with_stdio(false);

	uint_fast32_t N, Q, i;
	std::cin >> N >> Q;
	std::vector<uint_fast32_t> A(N), L(Q), R(Q);
	for (i = 0; i != N; ++i)
		std::cin >> A[i];
	for (i = 0; i != Q; ++i)
		std::cin >> L[i] >> R[i];

	output(Q, solve(Q, L, R, prepare(N, A)));
	return 0;
}
0