結果

問題 No.3205 Range Pairwise Xor Query
ユーザー amesyu
提出日時 2025-07-22 17:45:40
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 842 ms / 2,000 ms
コード長 1,715 bytes
コンパイル時間 402 ms
コンパイル使用メモリ 82,644 KB
実行使用メモリ 140,580 KB
最終ジャッジ日時 2025-07-22 17:45:54
合計ジャッジ時間 12,899 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

# Generated By Gemini 2.5 Pro

import sys

def main():
    # 入力を受け取る
    N, Q = map(int, sys.stdin.readline().split())
    A = list(map(int, sys.stdin.readline().split()))
    queries = [list(map(int, sys.stdin.readline().split())) for _ in range(Q)]

    # 制約からビット数は最大26 (0から25)
    MAX_BITS = 26

    # --- 1. 前計算: 累積和の構築 ---
    # bit_sum[k][i] は、A[0]からA[i-1]までのうち、kビット目が1の数の総数
    bit_sum = [[0] * (N + 1) for _ in range(MAX_BITS)]

    for k in range(MAX_BITS):
        for i in range(N):
            # 前の値を引き継ぐ
            bit_sum[k][i+1] = bit_sum[k][i]
            # A[i]のkビット目が1ならインクリメント
            if (A[i] >> k) & 1:
                bit_sum[k][i+1] += 1
    
    # --- 2. クエリ処理 ---
    for L, R in queries:
        # 1-indexedを0-indexedに調整
        L -= 1 
        
        total_xor_sum = 0
        length = R - L
        
        for k in range(MAX_BITS):
            # 区間[L, R) 内でkビット目が1の数を計算
            # bit_sum[k][R] は A[0]...A[R-1] の和
            # bit_sum[k][L] は A[0]...A[L-1] の和
            count1 = bit_sum[k][R] - bit_sum[k][L]
            
            # 区間内でkビット目が0の数を計算
            count0 = length - count1
            
            # このビットkが総和に寄与する額を計算
            # 1になるペアの数 (count0 * count1) にビットの重み (2^k) を掛ける
            contribution = count0 * count1 * (1 << k)
            total_xor_sum += contribution
            
        print(total_xor_sum)

if __name__ == "__main__":
    main()
0