結果

問題 No.3205 Range Pairwise Xor Query
ユーザー LyricalMaestro
提出日時 2025-08-16 01:20:49
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,010 ms / 2,000 ms
コード長 910 bytes
コンパイル時間 371 ms
コンパイル使用メモリ 82,776 KB
実行使用メモリ 173,688 KB
最終ジャッジ日時 2025-08-16 01:21:05
合計ジャッジ時間 14,993 ms
ジャッジサーバーID
(参考情報)
judge2 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #

# https://yukicoder.me/problems/no/3205


def main():
    N, Q = map(int, input().split())
    A = list(map(int, input().split()))
    queries = []
    for _ in range(Q):
        l, r = map(int, input().split())
        queries.append((l, r))

    arrays = [[0] * N for _ in range(26)]
    for i in range(26):
        for j in range(N):
            x = 1 if (1 << i) & A[j] > 0 else 0
            arrays[i][j] = x
    
    cum_arrays = [[0] * (N + 1) for _ in range(26)]
    for i in range(26):
        c = 0
        for j in range(N):
            c += arrays[i][j]
            cum_arrays[i][j + 1] = c
    
    for l, r in queries:
        answer = 0
        for i in range(26):
            one = cum_arrays[i][r] - cum_arrays[i][l - 1]
            zero = (r - l + 1) - one
            ans = one * zero
            answer += ans * (1 << i)
        print(answer)










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