#992172 (PyPy3) No.3524 二進範囲更新範囲和取得

提出ソース
結果

問題	No.3524 二進範囲更新範囲和取得
コンテスト
ユーザー	👑 p-adic
提出日時	2024-06-30 18:06:48
言語	PyPy3 (7.3.17) コンパイル: `pypy3 -mpy_compile _filename_` 実行: `pypy3 _filename_`
結果	AC
実行時間	1,745 ms / 2,000 ms
コード長	10,912 bytes
記録記録タグの例: 初AC ショートコード純ショートコード純主流ショートコード最速実行時間
コンパイル時間	216 ms
コンパイル使用メモリ	85,504 KB
実行使用メモリ	316,280 KB
平均クエリ数	1167.69
最終ジャッジ日時	2026-05-01 20:51:54
合計ジャッジ時間	44,987 ms
ジャッジサーバーID （参考情報）	judge3_1 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
other	AC * 45
権限があれば一括ダウンロードができます
ソースコード

raw source code
R=range
J=lambda:map(int,input().split())
N,B,Q=J()

#基点付きマグマ
class L:
	point=None
	def __init__(self,val):
		self.val = val
	def __eq__(self,other):
		return self.val==other.val
	def __imul__(self,other):
		self.val=(self*other).val #ユーザー定義
		return self
	def __mul__(self,other):
		return self.__class__([self.val[other.val[j]]for j in R(B)]) #ユーザー定義
	def copy(self):
		return self.__class__(self.val)
L.point=L([j for j in R(B)]) #ユーザー定義
#区間作用を行わない場合もL.pointの作用を区間積に用いるため、
#Lをdummyにせず自明群{1}などを用いる必要があることに注意。

#Lの基点が恒等変換に対応する左L作用つき集合
class S:
	def __init__(self,val):
		self.val = val
	def __eq__(self,other):
		return self.val==other.val
	def __ixor__(self,x): #左L作用
		self.val=x.val[self.val] #ユーザー定義
		return self
	def __xor__(self,x): #左L作用
		return self.__class__(x.val[self.val]) #ユーザー定義
	def copy(self):
		return self.__class__(self.val)

#Lの基点が恒等変換に対応する左L作用つき非可換N加群
class M:
	one=None
	def __init__(self,val):
		self.val = val[:]
	def __eq__(self,other):
		return self.val==other.val
	def __mul__(self,other):
		return self.__class__([self.val[j]+other.val[j]for j in R(B)]) #ユーザー定義
	def __pow__(self,n): #非可換N加群構造
		return self.__class__([c*n for c in self.val]) #ユーザー定義
	def __ixor__(self,x): #左L作用
		self=self ^ x #ユーザー定義
		return self
	def __xor__(self,x): #左L作用
		a=[0]*B
		for j in R(B):a[x.val[j]]+=self.val[j]
		return self.__class__(a) #ユーザー定義
	def copy(self):
		return self.__class__(self.val)
M.one=M([0]*B) #ユーザー定義

#A map from U \times S \times N to M satisfying suitable conditions
def Trans(u,s,n):
	u.val[s.val]+=n #User definition
	return u
def Univ(s,n):
	return Trans(M(0),s,n)

#Initialisation by an array O(N)

#Get O(1)
#InevalProduct O(N^{1/2}) using the monoidness of M

#IntervalSet O(N^{1/2}) using the non-commutative N-module structure on M
#IntervalAct (N^{1/2})
class EquivariantLazySqrtDecomposition:
	def __init__(self,a,N_sqrt=None):
		self.N = len(a)
		self.N_sqrt = int( self.N**0.5 ) + 1 if N_sqrt is None else N_sqrt
		self.N_d = ( self.N + self.N_sqrt - 1 ) // self.N_sqrt
		self.N_m = self.N_d * self.N_sqrt
		self.a = a #Remove [:] if unnecessary
		self.b = [M.one.copy()for d in R(self.N_d)]
		self.lazy_substitution = self.b[:]
		self.suspended = [False] * self.N_d
		self.lazy_action = [L.point.copy()for d in R(self.N_d)]
		self.a += [a[0]for d in R(self.N_m - self.N)]
		i_min = 0
		i_ulim = self.N_sqrt
		for d in R(self.N_d):
			for i in R(i_min,i_ulim):Trans(self.b[d],self.a[i],1)
			i_min = i_ulim
			i_ulim += self.N_sqrt

	def IntervalSet(self,i_start,i_final,s):
		i_min = max( i_start , 0 )
		i_ulim = min( i_final + 1 , self.N )
		d_0 = ( i_min + self.N_sqrt - 1 ) // self.N_sqrt
		d_1 = max( d_0 , i_ulim // self.N_sqrt )
		d_0_N_sqrt = d_0 * self.N_sqrt
		d_1_N_sqrt = d_1 * self.N_sqrt
		i_0 = min( d_0_N_sqrt , i_ulim )
		i_1 = max( i_0 , d_1_N_sqrt )
		if i_min < i_0:
			#Then d_0 > 0
			d_0_minus = d_0 - 1
			d_0_N_sqrt_minus = d_0_N_sqrt - self.N_sqrt
			if self.suspended[d_0_minus]:
				self.IntervalSet_Body( d_0_N_sqrt_minus , i_min , self.lazy_substitution[d_0_minus] )
				self.IntervalSet_Body( i_min , i_0 , s )
				self.IntervalSet_Body( i_0 , d_0_N_sqrt , self.lazy_substitution[d_0_minus] )
				self.suspended[d_0_minus] = False
				#Used the non-commutative N-module structure of M
				self.b[d_0_minus] = Trans( Trans( Univ( self.lazy_substitution[d_0_minus] , i_min - d_0_N_sqrt ) , s , i_0 - i_min ) , self.lazy_substitution[d_0_minus] , d_0_N_sqrt - i_0 )
			else:
				self.SolveSuspendedAction( d_0_minus )
				self.IntervalSet_Body( i_min , i_0 , s )
				self.b[d_0_minus] = ( self.IntervalProduct_Body( d_0_N_sqrt_minus , i_min ) * ( u ** ( i_0 - i_min ) ) ) * self.IntervalProduct_Body( i_0 , d_0_N_sqrt )
		power = Univ( s , self.N_sqrt )
		for d in R(d_0,d_1):
			self.b[d] = power
			self.lazy_substitution[d] = s
			self.suspended[d] = True
			self.lazy_action[d] = L.point.copy()
		if i_1 < i_ulim:
			#Then d_1 < self.N_d
			d_1_N_sqrt_plus = d_1_N_sqrt + self.N_sqrt
			self.b[d_1] = self.b[d_1]
			if self.suspended[d_1]:
				self.IntervalSet_Body( d_1_N_sqrt , i_1 , self.lazy_substitution[d_1] )
				self.IntervalSet_Body( i_1 , i_ulim , s )
				self.IntervalSet_Body( i_ulim , d_1_N_sqrt_plus , self.lazy_substitution[d_1] )
				self.suspended[d_1] = False
				#Used the non-commutative N-module structure of M
				self.b[d_1] = Trans( Trans( Univ( self.lazy_substitution[d_1] , i_1 - d_1_N_sqrt ) , s , i_ulim - i_1 ) , self.lazy_substitution[d_1] , d_1_N_sqrt_plus - i_ulim )
			else:
				self.SolveSuspendedAction( d_1 )
				self.IntervalSet_Body( i_1 , i_ulim , s )
				self.b[d_1] = Trans( self.IntervalProduct_Body( d_1_N_sqrt , i_1 ) , s , i_ulim - i_1 ) * self.IntervalProduct_Body( i_ulim , d_1_N_sqrt_plus )

	def IntervalAct(self,i_start,i_final,r):
		if r != L.point:
			i_min = max( i_start , 0 )
			i_ulim = min( i_final + 1 , self.N )
			d_0 = ( i_min + self.N_sqrt - 1 ) // self.N_sqrt
			d_1 = max( d_0 , i_ulim // self.N_sqrt )
			d_0_N_sqrt = d_0 * self.N_sqrt
			d_1_N_sqrt = d_1 * self.N_sqrt
			i_0 = min( d_0_N_sqrt , i_ulim )
			i_1 = max( i_0 , d_1_N_sqrt )
			if i_min < i_0:
				#Then d_0 > 0
				d_0_minus = d_0 - 1
				d_0_N_sqrt_minus = d_0_N_sqrt - self.N_sqrt;
				if self.suspended[d_0_minus]:
					s = self.lazy_substitution[d_0_minus] ^ r
					self.IntervalSet_Body( d_0_N_sqrt_minus , i_min , self.lazy_substitution[d_0_minus] )
					self.IntervalSet_Body( i_min , i_0 , s )
					self.IntervalSet_Body( i_0 , d_0_N_sqrt , self.lazy_substitution[d_0_minus] )
					self.suspended[d_0_minus] = False
					#Used the non-commutative N-module structure of M
					self.b[d_0_minus] = Trans( Trans( Univ( self.lazy_substitution[d_0_minus] , i_min - d_0_N_sqrt_minus ) , s , i_0 - i_min ) , self.lazy_substitution[d_0_minus] , d_0_N_sqrt - i_0 )
				else:
					if self.lazy_action[d_0_minus] == L.point:self.IntervalAct_Body( i_min , i_0 , r )
					else:
						self.IntervalAct_Body( d_0_N_sqrt_minus , i_min , self.lazy_action[d_0_minus] )
						self.IntervalAct_Body( i_min , i_0 , r * self.lazy_action[d_0_minus] )
						self.IntervalAct_Body( i_0 , d_0_N_sqrt , self.lazy_action[d_0_minus] )
						self.lazy_action[d_0_minus] = L.point.copy()
					self.SetProduct( d_0_minus )
			for d in R(d_0,d_1):
				self.b[d] = self.b[d] ^ r
				if self.suspended[d]:self.lazy_substitution[d] ^= r
				else:self.lazy_action[d] = r * self.lazy_action[d]
			if i_1 < i_ulim:
				#Then d_1 < self.N_d
				d_1_N_sqrt_plus = d_1_N_sqrt + self.N_sqrt
				if self.suspended[d_1]:
					s = self.lazy_substitution[d_1] ^ r
					self.IntervalSet_Body( d_1_N_sqrt , i_1 , self.lazy_substitution[d_1] )
					self.IntervalSet_Body( i_1 , i_ulim , s )
					self.IntervalSet_Body( i_ulim , d_1_N_sqrt_plus , self.lazy_substitution[d_1] )
					self.suspended[d_1] = False
					#Used the non-commutative N-module structure of M
					self.b[d_1] = Trans( Trans( Univ( self.lazy_substitution[d_1] , i_1 - d_1_N_sqrt ) , s , i_ulim - i_1 ) , self.lazy_substitution[d_1] , d_1_N_sqrt_plus - i_ulim )
				else:
					if self.lazy_action[d_1] == L.point:self.IntervalAct_Body( i_1 , i_ulim , r )
					else:
						self.IntervalAct_Body( d_1_N_sqrt , i_1 , self.lazy_action[d_1] )
						self.IntervalAct_Body( i_1 , i_ulim , r * self.lazy_action[d_1] )
						self.IntervalAct_Body( i_ulim , d_1_N_sqrt_plus , self.lazy_action[d_1] )
						self.lazy_action[d_1] = L.point.copy()
					self.SetProduct( d_1 )

	def Get(self,i):
		d = i // self.N_sqrt
		return self.lazy_substitution[d] if self.suspended[d]else self.a[i] ^ self.lazy_action[d]
	def IntervalProduct(self,i_start,i_final):
		i_min = max( i_start , 0 )
		i_ulim = min( i_final + 1 , self.N )
		d_0 = ( i_min + self.N_sqrt - 1 ) // self.N_sqrt
		d_1 = max( d_0 , i_ulim // self.N_sqrt )
		i_0 = min( d_0 * self.N_sqrt , i_ulim )
		i_1 = max( i_0 , d_1 * self.N_sqrt )
		answer = M.one.copy()
		if i_min < i_0:
			#Then d_0 > 0
			#Used the non-commutative N-module structure of M
			d_0_minus = d_0 - 1
			if self.suspended[d_0_minus]:Trans( answer , self.lazy_substitution[d_0_minus] , i_0 - i_min )
			else:answer = self.IntervalProduct_Body( i_min , i_0 ) ^ self.lazy_action[d_0_minus]
		for d in R(d_0,d_1):answer *= self.b[d]
		if i_1 < i_ulim:
			#Then d_1 < self.N_d
			#Used the non-commutative N-module structure of M
			if self.suspended[d_1]:Trans( answer , self.lazy_substitution[d_1] , i_ulim - i_1 )
			else:answer *= self.IntervalProduct_Body( i_1 , i_ulim ) ^ self.lazy_action[d_1]
		return answer

	#private:
	def SetProduct(self,d):
		self.b[d] = M.one.copy()
		i_min = d * self.N_sqrt
		i_ulim = i_min + self.N_sqrt
		for i in R(i_min,i_ulim):Trans( self.b[d] , self.a[i] , 1 )

	def SolveSuspendedSubstitution(self,d,s):
		i_min = d * self.N_sqrt
		self.IntervalSet_Body( i_min , i_min + self.N_sqrt , s )
		self.suspended[d] = False

	def IntervalSet_Body(self,i_min,i_ulim,s):
		for i in R(i_min,i_ulim):self.a[i] = s

	def SolveSuspendedAction(self,d):
		i_min = d * self.N_sqrt
		i_ulim = i_min + self.N_sqrt
		if self.lazy_action[d] != L.point:
			self.IntervalAct_Body( i_min , i_ulim , self.lazy_action[d] )
			self.b[d] ^= self.lazy_action[d]
			self.lazy_action[d] = L.point.copy()

	def IntervalAct_Body(self,i_min,i_ulim,r):
		for i in R(i_min,i_ulim):self.a[i] ^= r

	def IntervalProduct_Body(self,i_min,i_ulim):
		answer = M.one.copy()
		for i in R(i_min,i_ulim):Trans( answer , self.a[i] , 1 )
		return answer


#二分木をHL分解（二分木の定義から、indexの小さいnodeがheaviest）。
dfs=[1]
HL=[]
HL_inv=[0]*(N+1)
while dfs:
	temp = dfs.pop()
	if temp <= N:
		HL_inv[temp] = len(HL)
		HL+=[temp]
		dfs+=[temp << 1 | 1,temp << 1]
#二分木の各ノードの部分木に対応する区間の右端の計算。
Right = [0]*( N + 1 )
for i in R( N , 0 ,-1 ):
	temp = i << 1
	Right[i] = (Right[temp | 1] if temp < N else Right[temp])if temp <= N else HL_inv[i]
#HL分解後の配列をmod Bで計算。
A=[S(0)for i in R(N)]
for i in R( 1 , N + 1 ):A[HL_inv[i]].val = i%B
#写像の値への作用を遅延評価して頻度表を計算する平方分割。
lsd = EquivariantLazySqrtDecomposition( A , int( ( B * N ) ** 0.5 ) + 1 )
for _ in R( Q ):
	i,d=J()
	#作用する写像を構成。
	f=L([pow(j,d,B) + 1 for j in R( B )])
	for j in R( B ):
		if f.val[j]==B:f.val[j]=0
	#作用の遅延評価。
	lsd.IntervalAct( HL_inv[i] , Right[i] , f )
	#頻度表の区間和の計算。
	h = lsd.IntervalProduct( HL_inv[i] , Right[i] )
	#区間和の計算。
	answer = sum( h.val[j] * j for j in R( B ) ) % B
	#区間和の出力。
	print( answer )
yukicoder

結果

ソースコード
