結果
問題 |
No.1091 Range Xor Query
|
ユーザー |
|
提出日時 | 2022-04-13 14:38:04 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 673 ms / 2,000 ms |
コード長 | 1,359 bytes |
コンパイル時間 | 442 ms |
コンパイル使用メモリ | 82,292 KB |
実行使用メモリ | 110,344 KB |
最終ジャッジ日時 | 2024-12-23 12:37:07 |
合計ジャッジ時間 | 16,640 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 27 |
ソースコード
def segfunc(x,y): return x^y class SegTree: def __init__(self,x_list,init,segfunc): self.init=init self.segfunc=segfunc self.Height=len(x_list).bit_length()+1 self.Tree=[init]*(2**self.Height) self.num=2**(self.Height-1) for i in range(len(x_list)): self.Tree[2**(self.Height-1)+i]=x_list[i] for i in range(2**(self.Height-1)-1,0,-1): self.Tree[i]=segfunc(self.Tree[2*i],self.Tree[2*i+1]) def select(self,k): return self.Tree[k+self.num] def update(self,k,x): i=k+self.num self.Tree[i]=x while i>1: if i%2==0: self.Tree[i//2]=self.segfunc(self.Tree[i],self.Tree[i+1]) else: self.Tree[i//2]=self.segfunc(self.Tree[i-1],self.Tree[i]) i//=2 def query(self,l,r): result=self.init l+=self.num r+=self.num+1 while l<r: if l%2==1: result=self.segfunc(result,self.Tree[l]) l+=1 if r%2==1: result=self.segfunc(result,self.Tree[r-1]) l//=2 r//=2 return result n,q=map(int,input().split()) a=list(map(int,input().split())) seg=SegTree(a,0,segfunc) for _ in range(q): l,r=map(int,input().split()) print(seg.query(l-1,r-1))