結果

問題 No.3205 Range Pairwise Xor Query
ユーザー moon17
提出日時 2025-07-19 13:22:32
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,087 bytes
コンパイル時間 435 ms
コンパイル使用メモリ 82,576 KB
実行使用メモリ 266,976 KB
最終ジャッジ日時 2025-07-19 13:22:38
合計ジャッジ時間 5,356 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 5 TLE * 1 -- * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

(n,q),a,*e=[[*map(int,s.split())]for s in open(0)]
bt=[[0]for _ in range(26)]
for t in range(26):
  for i in a:
    bt[t]+=bt[t][-1]+(i>>t&1),
def Add(k):
  global res
  # for j in range(L,R+1):
  for t in range(26):
    nt=bt[t][R+1]-bt[t][L]
    if a[k]>>t&1:
      res+=(R-L+1-nt)*(1<<t)
    else:
      res+=nt*(1<<t)
def Del(k):
  global res
  # for j in range(L,R+1):
  for t in range(26):
    nt=bt[t][R+1]-bt[t][L]
    if a[k]>>t&1:
      res-=(R-L+1-nt)*(1<<t)
    else:
      res-=nt*(1<<t)
N=2*10**5+10 
#M=Sqrt(Q)個のバケットを作る
M=int(q**0.5)+1
bucket=[[] for i in range(M)]
#lを基準にして各バケットにqueを振り分け
for i,(l,r)in enumerate(e):
  l-=1;r-=1
  bucket[l*M//n]+=(l,r,i),
#各バケットをrの降順/昇順にソート
for i in range(M):
  if i&1:
    bucket[i].sort(key=lambda x:-x[1])
  else:
    bucket[i].sort(key=lambda x:x[1])
ans=[0]*q
L=R=res=0
Add(0)
for b in bucket:
  for l,r,i in b:
    while R<r:R+=1;Add(R)
    while L>l:L-=1;Add(L)
    while R>r:Del(R);R-=1
    while L<l:Del(L);L+=1
    ans[i]=res
print(*ans,sep='\n')
0