結果
問題 |
No.3205 Range Pairwise Xor Query
|
ユーザー |
|
提出日時 | 2025-07-18 21:42:18 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 763 ms / 2,000 ms |
コード長 | 643 bytes |
コンパイル時間 | 1,802 ms |
コンパイル使用メモリ | 198,784 KB |
実行使用メモリ | 106,368 KB |
最終ジャッジ日時 | 2025-07-18 21:42:38 |
合計ジャッジ時間 | 11,329 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 20 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; ll c2(ll a) { return ((a * (a-1))/2); } int main() { int N, Q;cin >> N >> Q; int K = 60; vector<ll> A(N+1, 0); vector<vector<ll>> C(N+1, vector<ll>(K, 0)); for (int i = 1;i <= N;i++) { cin >> A[i]; for (int j = 0;j < K;j++) { C[i][j] = C[i-1][j]; if ((1LL <<j) & A[i]) C[i][j]++; } } while (Q--) { ll ret = 0; int L, R;cin >> L >> R; for (int d = 0;d < K;d++) { ll cnt = c2((ll)(R-L+1)); ll ones = C[R][d] - C[L-1][d]; ll zeros = (ll)(R-L+1) - ones; cnt -= c2(ones) + c2(zeros); ret += (1LL<<d) * cnt; } cout << ret << endl; } }