結果

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

ソースコード

diff # 

(n,q),a,*e=[[*map(int,s.split())]for s in open(0)]
def Add(k):
  global res
  for j in range(L,R+1):
    # print(i,'ADD',j,k,res)
    res+=a[k]^a[j]
def Del(k):
  global res
  for j in range(L,R+1):
    # print(i,'DEL',j,k,res)
    res-=a[k]^a[j]
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