結果
問題 | No.2265 Xor Range Substring Sum Query |
ユーザー | とりゐ |
提出日時 | 2023-03-10 11:15:36 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,126 ms / 5,000 ms |
コード長 | 1,752 bytes |
コンパイル時間 | 1,041 ms |
コンパイル使用メモリ | 81,848 KB |
実行使用メモリ | 104,628 KB |
最終ジャッジ日時 | 2023-10-25 05:08:16 |
合計ジャッジ時間 | 33,657 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 33 ms
53,368 KB |
testcase_01 | AC | 33 ms
53,368 KB |
testcase_02 | AC | 44 ms
63,432 KB |
testcase_03 | AC | 64 ms
73,056 KB |
testcase_04 | AC | 1,341 ms
104,572 KB |
testcase_05 | AC | 1,362 ms
104,572 KB |
testcase_06 | AC | 1,427 ms
104,572 KB |
testcase_07 | AC | 1,424 ms
104,572 KB |
testcase_08 | AC | 1,348 ms
104,572 KB |
testcase_09 | AC | 1,875 ms
104,572 KB |
testcase_10 | AC | 1,942 ms
104,572 KB |
testcase_11 | AC | 1,917 ms
104,572 KB |
testcase_12 | AC | 1,910 ms
104,628 KB |
testcase_13 | AC | 1,933 ms
104,572 KB |
testcase_14 | AC | 1,616 ms
104,572 KB |
testcase_15 | AC | 1,589 ms
104,572 KB |
testcase_16 | AC | 1,604 ms
104,572 KB |
testcase_17 | AC | 1,585 ms
104,572 KB |
testcase_18 | AC | 980 ms
104,368 KB |
testcase_19 | AC | 974 ms
104,368 KB |
testcase_20 | AC | 2,100 ms
104,368 KB |
testcase_21 | AC | 2,126 ms
104,368 KB |
testcase_22 | AC | 872 ms
89,348 KB |
testcase_23 | AC | 902 ms
89,348 KB |
ソースコード
from sys import stdin input=lambda :stdin.readline()[:-1] class non_commutative_xor_segment_tree: def __init__(self,n,init,func,E): self.n=n self.N=1<<n self.m=n//2 self.func=func self.E=E self.s=1<<self.m self.node=[E]*self.N*(self.m+1) for i in range(self.N): self.node[i]=init[i] for i in range(1,self.m+1): for j in range(self.N): self.merge(i,j) def merge(self,i,j): L=j R=L^(1<<(i-1)) self.node[(i<<self.n)|j]=self.func(self.node[((i-1)<<self.n)|L],self.node[((i-1)<<self.n)|R]) def update(self,x,y): self.node[x]=y for i in range(1,self.m+1): l=(x>>i)<<i r=l+(1<<i) for j in range(l,r): self.merge(i,j) def query(self,L,R,X): R+=1 res=self.E for i in range(self.m): if (L>>i)&1 and L+(1<<i)<=R: res=self.func(res,self.node[(i<<self.n)|L^X]) L+=1<<i while L+self.s<=R: res=self.func(res,self.node[(self.m<<self.n)|L^X]) L+=self.s for i in range(self.m-1,-1,-1): if L+(1<<i)<=R: res=self.func(res,self.node[(i<<self.n)|L^X]) L+=1<<i return res mod=998244353 n=int(input()) S=input() N=1<<n pow11=[1]*N pow2=[1]*N for i in range(1,N): pow11[i]=pow11[i-1]*11%mod pow2[i]=pow2[i-1]*2%mod mask=(1<<20)-1 def op(L,R): L0=L>>20 L1=L&mask R0=R>>20 R1=R&mask res0=L0*pow11[R1]+R0*pow2[L1] res1=L1+R1 res0%=mod return (res0<<20)+res1 seg=non_commutative_xor_segment_tree(n,[(int(S[i])<<20)+1 for i in range(1<<n)],op,0) q=int(input()) for _ in range(q): query=list(map(int,input().split())) if query[0]==1: x,y=query[1:] seg.update(x,(y<<20)+1) else: L,R,X=query[1:] print(seg.query(L,R,X)>>20)