結果
問題 |
No.3205 Range Pairwise Xor Query
|
ユーザー |
![]() |
提出日時 | 2025-07-18 22:24:50 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 273 ms / 2,000 ms |
コード長 | 1,278 bytes |
コンパイル時間 | 3,390 ms |
コンパイル使用メモリ | 276,788 KB |
実行使用メモリ | 55,040 KB |
最終ジャッジ日時 | 2025-07-18 22:25:00 |
合計ジャッジ時間 | 8,725 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 20 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for (ll i = 0; i < (ll)(n); i++) #define ll long long const long long mod=998244353; const long long hmod=46216567629137; int main(){ cin.tie(0)->sync_with_stdio(0); cout.tie(0); int N,Q; cin>>N>>Q; ll A[N+1]; for(int i=1;i<=N;i++) cin>>A[i]; ll ruiseki[N+1][30]; for(int i=0;i<=N;i++){ for(int j=0;j<=26;j++) ruiseki[i][j]=0; } for(int i=1;i<=N;i++){ int wari=1; for(int j=0;j<=26;j++){ ruiseki[i][j]+=(A[i]/wari)%2; wari*=2; } } for(int i=1;i<=N;i++){ for(int j=0;j<=26;j++) ruiseki[i][j]+=ruiseki[i-1][j]; } ll all_A[N+1]; all_A[0]=0; for(int i=1;i<=N;i++){ all_A[i]=all_A[i-1]+A[i]; } int L[Q+1],R[Q+1]; for(int i=1;i<=Q;i++){ cin>>L[i]>>R[i]; ll now[30]; for(int j=0;j<=26;j++) now[j]=0; for(int j=0;j<=26;j++){ now[j]=ruiseki[R[i]][j]-ruiseki[L[i]-1][j]; } ll all=all_A[R[i]]-all_A[L[i]-1]; all*=(R[i]-L[i]); ll kake=1; for(int j=0;j<26;j++){ unsigned ll m=now[j]*(now[j]-1)*kake; all-=m; kake*=2; } cout<<all<<"\n"; } }