結果

問題 No.3581 分数対称差更新区間計数取得
コンテスト
ユーザー 👑 p-adic
提出日時 2026-06-28 13:28:42
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 3,170 ms / 10,000 ms
コード長 1,302 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 249 ms
コンパイル使用メモリ 85,504 KB
実行使用メモリ 105,344 KB
最終ジャッジ日時 2026-07-03 21:05:51
合計ジャッジ時間 33,837 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

R=range

class SqrtDecomposition:
	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 = [0]*self.N_d
		self.a += [0]*( 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):self.b[d] *= self.a[i]
			i_min = i_ulim
			i_ulim += self.N_sqrt

	def Set(self,i,u):
		d = i // self.N_sqrt
		self.b[d] += u - self.a[i]
		self.a[i] = u

	def Add(self,i,u):
		d = i // self.N_sqrt
		self.b[d] += u
		self.a[i] += u

	def IntervalSum(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 )
		return sum(self.a[i]for i in R(i_min,i_0)) + sum(self.b[d]for d in R(d_0,d_1)) + sum(self.a[i]for i in R(i_1,i_ulim))

J=lambda:map(int,input().split())
N=10**6+1
Q,*_=J()
A=SqrtDecomposition([0]*N)
for _ in R(Q):
	i,l,r=J()
	for d in R(1,i+1):
		if d*d>i:break
		A.Set(d,1-A.a[d]);j=i//d
		if d<j:A.Set(j,1-A.a[j])
	print(A.IntervalSum(l,r))
0