結果
問題 |
No.3205 Range Pairwise Xor Query
|
ユーザー |
![]() |
提出日時 | 2025-07-18 21:54:22 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 567 ms / 2,000 ms |
コード長 | 1,043 bytes |
コンパイル時間 | 5,864 ms |
コンパイル使用メモリ | 332,796 KB |
実行使用メモリ | 29,952 KB |
最終ジャッジ日時 | 2025-07-18 21:54:38 |
合計ジャッジ時間 | 12,815 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 20 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using i32 = int; using u32 = unsigned int; using i64 = long long; using u64 = unsigned long long; #define FAST_IO \ ios::sync_with_stdio(false); \ cin.tie(0); const i64 INF = 1001001001001001001; using Modint = atcoder::static_modint<998244353>; int main() { FAST_IO int N, Q; cin >> N >> Q; vector<int> A(N); for (int i = 0; i < N; ++i) { cin >> A[i]; } vector<int> L(Q), R(Q); for (int i = 0; i < Q; ++i) { cin >> L[i] >> R[i]; --L[i]; } int m = 30; vector<vector<int>> bs(m, vector<int>(N + 1, 0)); for (int b = 0; b < m; b ++) { for (int i = 0; i < N; i ++) { bs[b][i + 1] = bs[b][i]; if (A[i] & (1 << b)) { bs[b][i + 1]++; } } } for (int i = 0; i < Q; ++i) { i64 ans = 0; for (int b = 0; b < m; b ++) { i64 one = bs[b][R[i]] - bs[b][L[i]]; i64 zero = (R[i] - L[i]) - one; ans += (one * zero) * (1LL << b); } cout << ans << endl; } }