結果

問題 No.2265 Xor Range Substring Sum Query
コンテスト
ユーザー とりゐ
提出日時 2023-03-12 03:54:52
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 2,696 bytes
コンパイル時間 597 ms
コンパイル使用メモリ 82,080 KB
実行使用メモリ 347,820 KB
最終ジャッジ日時 2024-09-25 00:34:58
合計ジャッジ時間 7,869 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 1 RE * 1 TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

class non_commutative_xor_segment_tree:
  def __init__(self,n,init,ope,E):
    self.n=n # 配列のサイズは 2**n
    self.N=1<<n
    self.ope=ope # モノイドの演算
    self.E=E # モノイドの単位元

    self.node=[[E]*self.N for _ in range(n+1)]
    
    # テーブルを構築する．O(n*2**n)
    # node[i][j] には A_{j^0}, A_{j^1}, ..., A_{j^(2**i-1)} の情報を持たせる
    for j in range(self.N):
      self.node[0][j]=init[j] # init は初期配列
    for i in range(1,n+1):
      for j in range(self.N):
        self.node[i][j]=self.ope(self.node[i-1][j],self.node[i-1][j^(1<<(i-1))])

    # 各ノードの最終更新時刻を記録    
    self.last_update=[[0]*self.N for i in range(n+1)]
    self.time=1

    # 各ノードが更新すべき最新の時刻
    # 通常のセグ木と同じノードの持ち方(頂点番号の割り当て方)をする
    self.lazy=[0]*2*self.N
  
  def update(self,x,k):
    # A_x=k とセットする
    self.node[0][x]=k
    self.last_update[0][x]=self.time

    # ノードの更新するべき最新の時刻を上書き
    # この処理は O(n)
    for i in range(self.n+1):
      self.lazy[(x+self.N)>>i]=self.time
    
    self.time+=1

  def get(self,i,j):
    # 最新の node[i][j] を求める
    # last_update[i][j] がすでに最新(==self.lazy[(j+self.N)>>i])だったらそのまま返す
    if self.last_update[i][j]==self.lazy[(j+self.N)>>i]:
      return self.node[i][j]
    
    # そうでないとき，下にもぐって node[i][j] を求める
    self.node[i][j]=self.ope(self.get(i-1,j),self.get(i-1,j^(1<<(i-1))))
    # node[i][j] は最新であることを記録する
    self.last_update[i][j]=self.lazy[(j+self.N)>>i]
    return self.node[i][j]
  
  def query(self,L,R,X):
    # A_{L^X}, A_{(L+1)^X}, ..., A_{(R-1)^X} についての答えを求める
    # 高々 2n 個のノードを見る
    res=self.E
    for i in range(self.n+1):
      if (L>>i)&1 and L+(1<<i)<=R:
        res=self.ope(res,self.get(i,L^X))
        L+=1<<i
    for i in range(self.n,-1,-1):
      if L+(1<<i)<=R:
        res=self.ope(res,self.get(i,L^X))
        L+=1<<i
    return res

def op(L,R):
  res0=L[0]*pow11[R[1]]+R[0]*pow2[L[1]]
  res1=L[1]+R[1]
  return (res0%mod,res1)

mod=998244353

n=int(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

S=input()
seg=non_commutative_xor_segment_tree(n,[(int(S[i]),1) for i in range(1<<n)],op,(0,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,1))
  else:
    L,R,X=query[1:]
    print(seg.query(L,R+1,X)[0])
0