結果
問題 |
No.3205 Range Pairwise Xor Query
|
ユーザー |
|
提出日時 | 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 |
ソースコード
# 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()