結果
| 問題 |
No.3101 Range Eratosthenes Query
|
| コンテスト | |
| ユーザー |
 navel_tos
|
| 提出日時 | 2025-05-24 15:38:52 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 2,471 ms / 3,000 ms |
| コード長 | 8,912 bytes |
| コンパイル時間 | 1,140 ms |
| コンパイル使用メモリ | 82,712 KB |
| 実行使用メモリ | 342,560 KB |
| 最終ジャッジ日時 | 2025-05-24 15:39:53 |
| 合計ジャッジ時間 | 53,264 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 24 |
ソースコード
#yukicoder3101 Range Eratosthenes Query
#Wavelet Matrix
import heapq
class Wavelet_Matrix:
#前提mod: 完備辞書(Pythonアレンジ版)
class Fully_Indexable_Dictionary:
def __init__(self, B: list[int], quick_select = False):
self._N = N = len(B); self._x = x = 63; self._L = L = [0] * -(-N // x); self._C = C = [0] * -(-N // x); self._mask = [(1 << i) - 1 for i in range(1, x + 1)]; now = 0; self._count = [0] * 2; self._quick_select = (quick_select != False)
if self._quick_select: self._Q = Q = [-1] + [N] * N
for i in range(len(L)):
L[i] = self._count[1]
for k in range(x):
if now >= N: break
self._count[B[now]] += 1; C[i] += B[now] << k
if quick_select: pos = self._count[0] if B[now] == 0 else -self._count[1]; Q[pos] = now
now += 1
def __getitem__(self, i: int): return self._C[i // self._x] >> (i % self._x) & 1
def popcnt(self, N): N = (N & 0x5555555555555555) + ((N >> 1) & 0x5555555555555555); N = (N & 0x3333333333333333) + ((N >> 2) & 0x3333333333333333); N = (N & 0x0F0F0F0F0F0F0F0F) + ((N >> 4) & 0x0F0F0F0F0F0F0F0F); N = (N & 0x00FF00FF00FF00FF) + ((N >> 8) & 0x00FF00FF00FF00FF); N = (N & 0x0000FFFF0000FFFF) + ((N >> 16) & 0x0000FFFF0000FFFF); N = (N & 0x00000000FFFFFFFF) + ((N >> 32) & 0x00000000FFFFFFFF); return N
def rank(self, i, num = 0): k, t = i // self._x, i % self._x; one = self._L[k] + self.popcnt( self._C[k] & self._mask[t] ); return 0 if i < 0 else one if num else 1 + i - one
def select(self, k, num = 0): #rank(i,num) == kとなるi なければN O(logN)
if k > self._count[num] or k == 0: return -1 if k == 0 else self._N
if self._quick_select: return self._Q[k] if num == 0 else self._Q[-k]
ok, ng = self._N, -1
while abs(ok - ng) > 1: mid = (ok + ng) // 2; ok, ng = (mid, ng) if self.rank(mid, num) >= k else (ok, mid)
return ok
def stable_sort(self, i, num = 0): return self.rank(i - 1, 0) if num == 0 else self._count[0] + self.rank(i - 1, 1)
def range_sort(self, Lt, Rt, num = 0): z = self._count[0]; return (self.rank(Lt - 1, 0), self.rank(Rt - 1, 0)) if num == 0 else (z + self.rank(Lt - 1, 1), z + self.rank(Rt - 1, 1))
def __init__(self, A: list[int], quick_select = True):
self._N = N = len(A); self._T, X, Y, Z = A[:], 1, [0] * N, [0] * N
for num in A: X = max(num, X); assert num >= 0, 'non - negative int only.'
self._logX = logX = X.bit_length(); self._B = B = [None] * logX; self._D = D = dict(); self._has_bit = has_bit = lambda S, x: S >> x & 1
for x in range(logX - 1, -1, -1):
y = z = 0
for i in range(N): Y[i] = has_bit(self._T[i], x); z += 1 if Y[i] == 0 else 0
B[x] = self.Fully_Indexable_Dictionary(Y, quick_select)
for i in range(N):
if Y[i] == 0: Z[y] = self._T[i]; y += 1
elif Y[i] == 1: Z[z] = self._T[i]; z += 1
self._T, Z = Z, self._T
for i in range(N):
if self._T[i] not in D: D[self._T[i]] = i
def __getitem__(self, i: int): #復元 O(logX)
i %= self._N; c = 0
for k in range(self._logX - 1, -1, -1): b = self._B[k][i]; c += b << k; i = self._B[k].stable_sort(i, b)
return c
def rank(self, Lt, Rt, x): #半開区間[Lt:Rt)のxの出現回数
for k in range(self._logX - 1, -1, -1): c = self._has_bit(x, k); Lt, Rt = self._B[k].range_sort(Lt, Rt, c)
return Rt - Lt
def select(self, time, x): #time番目のxの位置 配列外は-1やNを返す
if time == 0 or x not in self._D: return -1
p, c = self._D[x] + (time - 1), 0
if p >= self._N: return self._N
for k in range(self._logX):
b = self._has_bit(x, k); c += b << k
if b == 1: p -= self._B[k]._count[0]
p = self._B[k].select(p + 1, b)
if p not in range(0, self._N): return self._N
return p if x == c else self._N
def get_min(self, Lt, Rt, time): #sorted( T[Lt:Rt) )の小さい方からt番目
if not 0 < time <= Rt - Lt: return -1
t = time - 1
for k in range(self._logX - 1, -1, -1): d = self._B[k].rank(Rt - 1, 0) - self._B[k].rank(Lt - 1, 0); b, t = (0, t) if t < d else (1, t - d); Lt, Rt = self._B[k].range_sort(Lt, Rt, b)
return self._T[Lt + t]
def range_freq(self, Lt, Rt, time): #頻出順にt個 O((Rt - Lt) logX)
Q = [(~(Rt - Lt), ~(self._logX - 1), 0, Lt, Rt)]; ans = []
while Q and len(ans) < time:
_, k, c, Lt, Rt = heapq.heappop(Q); k = ~k
if not 0 <= Lt < Rt <= self._N: continue
if k == -1: ans.append((c, Rt - Lt)); continue
for d in range(2):
a, b = self._B[k].range_sort(Lt, Rt, d)
if b - a > 0: heapq.heappush(Q, (~(b - a), ~(k - 1), c + (d << k), a, b))
return ans
def count(self, Lt, Rt, xL, xR): #T[Lt:Rt)中に出現する、xL <= T[i] < xR の個数
if not 0 <= Lt < Rt <= self._N or not 0 <= xL <= xR: return 0
ans = Rt - Lt
if xL > 0:
Q = [(0, self._logX - 1, Lt, Rt)]
while Q:
c, k, L, R = Q.pop()
if c + (1 << (k + 1)) - 1 < xL: ans -= R - L; continue
if k == -1: break
for d in range(1, -1, -1):
a, b = self._B[k].range_sort(L, R, d)
if b - a > 0: Q.append((c + (d << k), k - 1, a, b))
if xR <= (1 << self._logX) - 1:
Q = [(0, self._logX - 1, Lt, Rt)]
while Q:
c, k, L, R = Q.pop()
if c >= xR: ans -= R - L; continue
if k == -1: break
for d in range(2):
a, b = self._B[k].range_sort(L, R, d)
if b - a > 0: Q.append((c + (d << k), k - 1, a, b))
return ans
#T[Lt:Rt)中で、xL <= T[i] < xRを満たす 最小 / 最大値(条件を満たさなければ -1)
def next_value(self, Lt, Rt, xL, xR, return_max = False):
Q = [(0, self._logX - 1, Lt, Rt)]; R = range(2) if return_max else range(1, -1, -1)
while Q:
c, k, Lt, Rt = Q.pop()
if not 0 <= Lt < Rt <= self._N or c + (1 << (k + 1)) - 1 < xL or c >= xR: continue
if k == -1: return c
for d in R:
a, b = self._B[k].range_sort(Lt, Rt, d)
if b - a > 0: Q.append((c + (d << k), k - 1, a, b))
else: return -1
def next_index(self, Lt, x): #T[Lt:)内にはじめて存在するxの添字
c = self.rank(0, Lt, x); return self.select(c + 1, x)
def intersect(self, L1, R1, L2, R2): #T[L1:R1)とT[L2:R2)の共通要素を取り出す
Q = [(0, self._logX - 1, L1, R1, L2, R2)]; ans = []
while Q:
c, k, L1, R1, L2, R2 = Q.pop()
if not 0 <= L1 < R1 <= self._N or not 0 <= L2 < R2 <= self._N: continue
if k == -1: ans.append((c, min( R1 - L1, R2 - L2 ))); continue
for d in range(1, -1, -1):
a1, b1 = self._B[k].range_sort(L1, R1, d); a2, b2 = self._B[k].range_sort(L2, R2, d)
if b1 - a1 > 0 and b2 - a2 > 0: Q.append((c + (d << k), k - 1, a1, b1, a2, b2))
return ans
#愚直解 N = Ri - Li として O(NloglogN)
def brute(Li, Ri):
E = list(range(Li, Ri + 1))
ans = 0
for i in range(Li, Ri + 1):
if E[i - Li] == i:
ans += 1
for k in range(i, Ri + 1, i):
E[k - Li] = i
return ans
#値nが食べられる条件は: [Li, Ri]内の最小約数がちょうどnであること
#これの正当性を確認しておく
def check(Li, Ri):
E = [[] for _ in range(Ri + 1)]
for n in range(1, Ri + 1):
for k in range(n, Ri + 1, n):
E[k].append(n)
ans = 0
for n in range(Li, Ri + 1):
assert E[n][-1] == n
if len(E[n]) == 1 or E[n][-2] < Li: ans += 1
return ans
#たぶん合ってそう なので最大約数表を作成
#最小素因数表は簡単に作れるのでそれを流用
E = list(range(10 ** 6 + 1))
for p in range(2, 10 ** 6 + 1):
if E[p] == p:
for k in range(p, 10 ** 6 + 1, p):
E[k] = min(E[k], p)
for n in range(1, 10 ** 6 + 1):
E[n] = n // E[n]
E[1] = 0 #便宜上
#静配列Eを与える。以下のクエリを処理せよ:
#[Li, Ri]に含まれる、最小値がLi未満の値の個数を答えよ。
#クエリをLiでソートすれば解けるだろうが、ライブラリチェックしたい
#のでWavelet Matrixで殴る
WM = Wavelet_Matrix(E, True)
for _ in range( Q := int(input()) ):
Li, Ri = map(int, input().split())
print( WM.count(Li, Ri + 1, 0, Li) )