ライブラリ
| 投稿者 | akazuki8 |
|---|---|
| 言語 | PyPy3 |
| 更新日時 (JST) | 2026-10-16 04:11:19 |
| サイズ | 68,430 Byte |
| 参照URL | |
日時はサーバーが記録したものです。更新すると更新日時が変わるので、不都合がある場合は新しく投稿してください。
import math
import collections
import heapq
import bisect
import sys
import copy
import itertools
from collections import defaultdict
import random
sys.setrecursionlimit(6*10**5)
from sortedcontainers import SortedSet, SortedList, SortedDict
import hashlib
def new_hasher():
return hashlib.blake2b(digest_size=16)
'''
h = new_hasher()
h.update(s.encode())
S = h.digest()
'''
def I():return input()
def II():return int(input())
def IS():return input().split()
def MI():return map(int,input().split())
def LS():return list(input().split())
def LI():return list(map(int,input().split()))
def LC():return list(input())
#0index
def MI0():return map(lambda x:int(x)-1,input().split())
def LI0():return list(map(lambda x:int(x)-1,input().split()))
mod=998244353
MOD=10**9+7
#階乗
def Factorial(n,mod):
c=1
for i in range(2,n+1):
c*=i
c%=mod
return c
#階乗リスト
def FactorialList(n,mod):
c=[1,1]
for i in range(2,n+1):
c.append(c[-1]*i%mod)
return c
#コンビネーション
#階乗が前計算してある時はそれを使う
def CMB(n,k):
if n==k or k==0:
return 1
c=1
for i in range(k+1,n+1):
c*=i
c%=mod
d=1
for i in range(2,n-k+1):
d*=i
d%=mod
return c*pow(d,-1,mod)%mod
#最小公倍数
def LCM(a,b):
return math.gcd(a*b//math.gcd(a,b))
#素数列挙
def eratosthenes(n):
isPrimes = [True] * (n+1)
isPrimes[0], isPrimes[1] = False, False
for i in range(2, int(n**0.5)+1):
if isPrimes[i]:
for j in range(2*i, n+1, i):
isPrimes[j] = False
return [i for i in range(2, n+1) if isPrimes[i]]
#二つの線分の交差判定(a=[2,-1],b=[-3,-3]などで与える）
def max_min_cross(p1, p2, p3, p4):
min_ab, max_ab = min(p1, p2), max(p1, p2)
min_cd, max_cd = min(p3, p4), max(p3, p4)
if min_ab > max_cd or max_ab < min_cd:
return False
return True
def cross_judge(a, b, c, d):
# x座標による判定
if not max_min_cross(a[0], b[0], c[0], d[0]):
return False
# y座標による判定
if not max_min_cross(a[1], b[1], c[1], d[1]):
return False
tc1 = (a[0] - b[0]) * (c[1] - a[1]) + (a[1] - b[1]) * (a[0] - c[0])
tc2 = (a[0] - b[0]) * (d[1] - a[1]) + (a[1] - b[1]) * (a[0] - d[0])
td1 = (c[0] - d[0]) * (a[1] - c[1]) + (c[1] - d[1]) * (c[0] - a[0])
td2 = (c[0] - d[0]) * (b[1] - c[1]) + (c[1] - d[1]) * (c[0] - b[0])
return tc1 * tc2 <= 0 and td1 * td2 <= 0
#dfs(start-goal経路)
import sys
sys.setrecursionlimit(6*10**5)
def dfs(start, goal, adj_list):
visited = [False] * len(adj_list)
path = []
def dfs_util(node):
if node == goal:
path.append(node)
return True
visited[node] = True
path.append(node)
for neighbor in adj_list[node]:
if not visited[neighbor]:
if dfs_util(neighbor):
return True
path.pop()
return False
if dfs_util(start):
return path
else:
return None
#根付き木の深さ、辺の長さ1のrootからの距離
def bfs(graph,root):
a=[-1 for i in range(len(graph))]
now={root*75}
a[root]=0
c=1
while now:
new=set()
for i in now:
for j in graph[i//75]:
if a[j]==-1:
new.add(j*75)
a[j]=c
now=new
c+=1
return a
#ダイクストラ法
import heapq
def dijkstra(graph, start=0):
num_node = len(graph)
inf = float('inf')
distances = [inf] * num_node
distances[start] = 0
pq = [(0, start)]
while pq:
current_distance, current_node = heapq.heappop(pq)
if current_distance > distances[current_node]:
continue
for neighbor, weight in graph[current_node]:
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(pq, (distance, neighbor))
return distances
#BIT
class BIT:
def __init__(self, n):
self.size=n
self.tree = [0] * (n+1)
def add(self, i,x):
while i <= self.size:
self.tree[i] += x
i += i & -i
def sum(self, i):
total = 0
while i >0:
total += self.tree[i]
i -= i & -i
return total
#転倒数(BITも貼る)
def InversionNumberByBIT(A):
ans = 0
Bit = BIT(len(A))
for i in range(len(A)):
ans += i - Bit.sum(A[i])
Bit.add(A[i], 1)
return ans
#座圧
def zaatsu(before_list):
set_sort = sorted(list(set(before_list)))
rank = {x:i+1 for i,x in enumerate(set_sort)}
after_list = []
for tmp in before_list:
after_list.append(rank[tmp])
return after_list
#座圧して転倒数を計算
def InversionNumberByBIT2(A):
return InversionNumberByBIT(zaatsu(A))
#約数列挙
def divisor(n):
sq = n**0.5
border = int(sq)
table = []
bigs = []
for small in range(1, border+1):
if n%small == 0:
table.append(small)
big = n//small
bigs.append(big)
if border == sq:
bigs.pop()
table += reversed(bigs)
return table
#遅延pq、削除命令がO(1)
import heapq
class LazyHeap:
def __init__(self, A):
self.heap = A[:]
heapq.heapify(self.heap)
self.deleted = {}
def push(self, x):
heapq.heappush(self.heap, x)
def erase(self, x):
self.deleted[x] = self.deleted.get(x, 0) + 1
def _clean(self):
while self.heap:
x = self.heap[0]
if x not in self.deleted:
break
if self.deleted[x] == 1:
del self.deleted[x]
else:
self.deleted[x] -= 1
heapq.heappop(self.heap)
def top(self):
self._clean()
return self.heap[0]
def pop(self):
self._clean()
return heapq.heappop(self.heap)
def empty(self):
self._clean()
return len(self.heap) == 0
#素因数分解
def prime_factorize(n):
a = []
while n % 2 == 0:
a.append(2)
n //= 2
f = 3
while f * f <= n:
if n % f == 0:
a.append(f)
n //= f
else:
f += 2
if n != 1:
a.append(n)
return a
#素因数分解した結果を辞書形式で返す
import collections
def prime_factorize2(n):
return collections.Counter(prime_factorize(n))
#最大増加部分列(長さのみ)
def LIS(a, inf = 1e18) :
n = len(a)
dp = [inf] * n
for i in range(n) :
pos = bisect.bisect_left(dp, a[i])
dp[pos] = a[i]
return bisect.bisect_left(dp, inf)
#行列累乗
def mat_mul(A, B, mod):
n = len(A)
m = len(B[0])
p = len(B)
C = [[0] * m for _ in range(n)]
for i in range(n):
for k in range(p):
if A[i][k] == 0:
continue
a = A[i][k]
for j in range(m):
C[i][j] = (C[i][j] + a * B[k][j]) % mod
return C
def mat_pow(A, e, mod):
n = len(A)
R = [[0] * n for _ in range(n)]
for i in range(n):
R[i][i] = 1
while e:
if e & 1:
R = mat_mul(R, A, mod)
A = mat_mul(A, A, mod)
e >>= 1
return R
#Aが一次元の行列の場合
#A_n=M^(n-1)A_1 をもとめる。
def A_n(A_1,M,n,mod):
S=[[A_1[i]] for i in range(len(A_1))]
return mat_mul(S,mat_pow(M,n-1,mod),mod)
#UnionFind
from collections import defaultdict
class UnionFind:
def __init__(self, n):
self.n = n
self.parents = [-1] * n
def find(self, x):
if self.parents[x] < 0:
return x
else:
self.parents[x] = self.find(self.parents[x])
return self.parents[x]
def union(self, x, y):
x = self.find(x)
y = self.find(y)
if x == y:
return
if self.parents[x] > self.parents[y]:
x, y = y, x
self.parents[x] += self.parents[y]
self.parents[y] = x
def size(self, x):
return -self.parents[self.find(x)]
def same(self, x, y):
return self.find(x) == self.find(y)
#注O(n)
def members(self, x):
root = self.find(x)
return [i for i in range(self.n) if self.find(i) == root]
def roots(self):
return [i for i, x in enumerate(self.parents) if x < 0]
def group_count(self):
return len(self.roots())
def all_group_members(self):
group_members = defaultdict(list)
for member in range(self.n):
group_members[self.find(member)].append(member)
return group_members
def __str__(self):
return '\n'.join(f'{r}: {m}' for r, m in self.all_group_members().items())
#クラスカル法（UFも貼ること）
def kruskal(adj_list):
edges = []
n = len(adj_list)
for u in range(n):
for v, weight in adj_list[u]:
if u < v:
edges.append((weight, u, v))
edges.sort()
uf = UnionFind(n)
mst_weight = 0
mst_edges = []
for weight, u, v in edges:
if uf.find(u) != uf.find(v):
uf.union(u, v)
mst_weight += weight
mst_edges.append((u, v))
return mst_weight, mst_edges
#重み付きUF
class WeightedUnionFind:
def __init__(self, n):
self.par = [i for i in range(n+1)]
self.rank = [0] * (n+1)
# 根への距離を管理
self.weight = [0] * (n+1)
# 検索
def find(self, x):
if self.par[x] == x:
return x
else:
y = self.find(self.par[x])
# 親への重みを追加しながら根まで走査
self.weight[x] += self.weight[self.par[x]]
self.par[x] = y
return y
# 併合
def union(self, x, y, w):
rx = self.find(x)
ry = self.find(y)
# xの木の高さ < yの木の高さ
if self.rank[rx] < self.rank[ry]:
self.par[rx] = ry
self.weight[rx] = w - self.weight[x] + self.weight[y]
# xの木の高さ ≧ yの木の高さ
else:
self.par[ry] = rx
self.weight[ry] = -w - self.weight[y] + self.weight[x]
# 木の高さが同じだった場合の処理
if self.rank[rx] == self.rank[ry]:
self.rank[rx] += 1
# 同じ集合に属するか
def same(self, x, y):
return self.find(x) == self.find(y)
# xからyへのコスト
def diff(self, x, y):
return self.weight[x] - self.weight[y]
#なもりグラフの循環している部分を列挙
def get_cycles(to):
n = len(to)
state = [0] * n # 0:未訪問, 1:探索中, 2:探索終了
cycles = []
for s in range(n):
if state[s]:
continue
v = s
pos = {}
path = []
while state[v] == 0:
state[v] = 1
pos[v] = len(path)
path.append(v)
v = to[v]
if state[v] == 1 and v in pos:
cycles.append(path[pos[v]:])
for x in path:
state[x] = 2
return cycles
#segfunc
def segfunc(x,y):return x+y
def segfunc(x,y):return x*y
#セグ木
class SegTree:
def __init__(self, init_val, segfunc, ide_ele):
n = len(init_val)
self.segfunc = segfunc
self.ide_ele = ide_ele
self.num = 1
while self.num < n:
self.num <<= 1
self.tree = [ide_ele] * (2 * self.num)
for i in range(n):
self.tree[self.num + i] = init_val[i]
for i in range(self.num - 1, 0, -1):
self.tree[i] = self.segfunc(
self.tree[i << 1],
self.tree[i << 1 | 1]
)
def add(self, k, x):
k += self.num
self.tree[k] += x
while k > 1:
k >>= 1
self.tree[k] = self.segfunc(
self.tree[k << 1],
self.tree[k << 1 | 1]
)
def update(self, k, x):
k += self.num
self.tree[k] = x
while k > 1:
k >>= 1
self.tree[k] = self.segfunc(
self.tree[k << 1],
self.tree[k << 1 | 1]
)
def query(self, l, r):
res = self.ide_ele
l += self.num
r += self.num
while l < r:
if l & 1:
res = self.segfunc(res, self.tree[l])
l += 1
if r & 1:
r -= 1
res = self.segfunc(res, self.tree[r])
l >>= 1
r >>= 1
return res
def bisect_left(self, x):
l = 0
r = self.num
while l < r:
m = (l + r) >> 1
if self.tree[self.num + m] < x:
l = m + 1
else:
r = m
return l
def bisect_right(self, x):
l = 0
r = self.num
while l < r:
m = (l + r) >> 1
if self.tree[self.num + m] <= x:
l = m + 1
else:
r = m
return l
#遅延セグ木（区間加算用）
class LazySegTree_RAQ:
def __init__(self, init_val, segfunc, ide_ele):
n = len(init_val)
self.n = n
self.segfunc = segfunc
self.ide_ele = ide_ele
self.num = 1
while self.num < n:
self.num <<= 1
self.tree = [ide_ele] * (2 * self.num)
self.lazy = [0] * (2 * self.num)
self.mx = [float("-inf")] * (2 * self.num)
for i in range(n):
self.tree[self.num + i] = init_val[i]
self.mx[self.num + i] = init_val[i]
for i in range(self.num - 1, 0, -1):
self.tree[i] = self.segfunc(
self.tree[2 * i],
self.tree[2 * i + 1]
)
self.mx[i] = max(
self.mx[2 * i],
self.mx[2 * i + 1]
)
def gindex(self, l, r):
l += self.num
r += self.num
# bit_length() を使わない
lm = l
while lm & -lm != lm:
lm -= lm & -lm
rm = r
while rm & -rm != rm:
rm -= rm & -rm
lm = l >> 1
rm = r >> 1
while r > l:
if l <= lm:
yield l
if r <= rm:
yield r
r >>= 1
l >>= 1
while l:
yield l
l >>= 1
def propagates(self, *ids):
for i in reversed(ids):
v = self.lazy[i]
if v == 0:
continue
self.lazy[i] = 0
self.lazy[2 * i] += v
self.lazy[2 * i + 1] += v
self.tree[2 * i] += v
self.tree[2 * i + 1] += v
self.mx[2 * i] += v
self.mx[2 * i + 1] += v
def lazy_push(self, k):
v = self.lazy[k]
if v == 0:
return
self.lazy[k] = 0
self.lazy[2 * k] += v
self.lazy[2 * k + 1] += v
self.tree[2 * k] += v
self.tree[2 * k + 1] += v
self.mx[2 * k] += v
self.mx[2 * k + 1] += v
def add(self, l, r, x):
ids = self.gindex(l, r)
l += self.num
r += self.num
while l < r:
if l & 1:
self.lazy[l] += x
self.tree[l] += x
self.mx[l] += x
l += 1
if r & 1:
r -= 1
self.lazy[r] += x
self.tree[r] += x
self.mx[r] += x
l >>= 1
r >>= 1
for i in ids:
self.tree[i] = (
self.segfunc(
self.tree[2 * i],
self.tree[2 * i + 1]
) + self.lazy[i]
)
self.mx[i] = (
max(
self.mx[2 * i],
self.mx[2 * i + 1]
) + self.lazy[i]
)
def query(self, l, r):
self.propagates(*self.gindex(l, r))
res = self.ide_ele
l += self.num
r += self.num
while l < r:
if l & 1:
res = self.segfunc(res, self.tree[l])
l += 1
if r & 1:
res = self.segfunc(res, self.tree[r - 1])
l >>= 1
r >>= 1
return res
def bisect_left(self, x):
if self.mx[1] < x:
return self.n
k = 1
while k < self.num:
self.lazy_push(k)
if self.mx[2 * k] >= x:
k *= 2
else:
k = 2 * k + 1
return min(k - self.num, self.n)
def bisect_right(self, x):
if self.mx[1] <= x:
return self.n
k = 1
while k < self.num:
self.lazy_push(k)
if self.mx[2 * k] > x:
k *= 2
else:
k = 2 * k + 1
return min(k - self.num, self.n)
#遅延セグ木（区間更新用）
class LazySegTree_RUQ:
def __init__(self, init_val, segfunc, ide_ele):
n = len(init_val)
self.n = n
self.segfunc = segfunc
self.ide_ele = ide_ele
self.num = 1
while self.num < n:
self.num <<= 1
self.tree = [ide_ele] * (2 * self.num)
# lazyの値
self.lazy = [0] * (2 * self.num)
# そのノードに区間代入が存在するか
self.lazy_flag = [False] * (2 * self.num)
# bisect用の区間最大値
self.mx = [0] * (2 * self.num)
for i in range(n):
self.tree[self.num + i] = init_val[i]
self.mx[self.num + i] = init_val[i]
# num以降のダミー部分
for i in range(n, self.num):
self.mx[self.num + i] = -10**30
for i in range(self.num - 1, 0, -1):
self.tree[i] = self.segfunc(
self.tree[2 * i],
self.tree[2 * i + 1]
)
self.mx[i] = max(
self.mx[2 * i],
self.mx[2 * i + 1]
)
def gindex(self, l, r):
l += self.num
r += self.num
low_l = l & -l
low_r = r & -r
lm = (l // low_l) // 2 * low_l
rm = (r // low_r) // 2 * low_r
while r > l:
if l <= lm:
yield l
if r <= rm:
yield r
l >>= 1
r >>= 1
while l:
yield l
l >>= 1
def propagates(self, *ids):
for i in reversed(ids):
if not self.lazy_flag[i]:
continue
v = self.lazy[i]
self.lazy_flag[i] = False
self.lazy[2 * i] = v
self.lazy[2 * i + 1] = v
self.lazy_flag[2 * i] = True
self.lazy_flag[2 * i + 1] = True
self.tree[2 * i] = v
self.tree[2 * i + 1] = v
self.mx[2 * i] = v
self.mx[2 * i + 1] = v
def lazy_push(self, k):
if not self.lazy_flag[k]:
return
v = self.lazy[k]
self.lazy_flag[k] = False
self.lazy[2 * k] = v
self.lazy[2 * k + 1] = v
self.lazy_flag[2 * k] = True
self.lazy_flag[2 * k + 1] = True
self.tree[2 * k] = v
self.tree[2 * k + 1] = v
self.mx[2 * k] = v
self.mx[2 * k + 1] = v
def update(self, l, r, x):
ids = self.gindex(l, r)
l += self.num
r += self.num
while l < r:
if l & 1:
self.lazy[l] = x
self.lazy_flag[l] = True
self.tree[l] = x
self.mx[l] = x
l += 1
if r & 1:
r -= 1
self.lazy[r] = x
self.lazy_flag[r] = True
self.tree[r] = x
self.mx[r] = x
l >>= 1
r >>= 1
for i in ids:
if i == 0:
continue
if self.lazy_flag[i]:
self.tree[i] = self.lazy[i]
self.mx[i] = self.lazy[i]
else:
self.tree[i] = self.segfunc(
self.tree[2 * i],
self.tree[2 * i + 1]
)
self.mx[i] = max(
self.mx[2 * i],
self.mx[2 * i + 1]
)
def query(self, l, r):
self.propagates(*self.gindex(l, r))
res = self.ide_ele
l += self.num
r += self.num
while l < r:
if l & 1:
res = self.segfunc(res, self.tree[l])
l += 1
if r & 1:
res = self.segfunc(res, self.tree[r - 1])
l >>= 1
r >>= 1
return res
def bisect_left(self, x):
"""
x 以上になる最初の位置
O(log N)
配列が単調非減少であることが必要。
"""
if self.n == 0:
return 0
if self.mx[1] < x:
return self.n
k = 1
while k < self.num:
self.lazy_push(k)
if self.mx[2 * k] >= x:
k *= 2
else:
k = 2 * k + 1
ans = k - self.num
if ans >= self.n:
return self.n
return ans
def bisect_right(self, x):
"""
x より大きくなる最初の位置
O(log N)
配列が単調非減少であることが必要。
"""
if self.n == 0:
return 0
if self.mx[1] <= x:
return self.n
k = 1
while k < self.num:
self.lazy_push(k)
if self.mx[2 * k] > x:
k *= 2
else:
k = 2 * k + 1
ans = k - self.num
if ans >= self.n:
return self.n
return ans
#FunctionalGraph（ダブリングなど）
class FunctionalGraph:
def __init__(self, n: int, next: list[int]) -> None:
self.n = n
self.sqrt_n = int(n**0.5)
self.nexts = next
self.jumps = [-1] * self.n
self.visited = [False] * self.n
self.cycles = [-1] * self.n
self.cycles_index = [-1] * self.n
self.calc_cycles()
self.calc_jumps()
def calc_jumps(self) -> None:
for s in range(self.n):
now = s
for _ in range(self.sqrt_n):
now = next[now]
self.jumps[s] = now
def calc_cycles(self) -> None:
for s in range(self.n):
if not self.visited[s]:
path, cycle = self.dfs(s)
for i, v in enumerate(cycle):
self.cycles[v] = cycle
self.cycles_index[v] = i
def dfs(self, s: int) -> tuple[list[int], list[int]]:
stack = [s]
path = [s]
cycle = []
self.visited[s] = True
while stack:
now = stack.pop()
next = self.nexts[now]
if not self.visited[next]:
stack.append(next)
self.visited[next] = True
path.append(next)
next = self.nexts[path[-1]]
index = 0
while index < len(path):
if path[index] == next:
path, cycle = path[:index], path[index:]
break
index += 1
return path, cycle
def get_next(self, s: int, k: int) -> int:
now = s
while self.cycles[now] == -1 and k > 0:
if k >= self.sqrt_n:
k -= self.sqrt_n
now = self.jumps[now]
else:
k -= 1
now = self.nexts[now]
if k == 0:
return now
cycle_len = len(self.cycles[now])
now = self.cycles[now][(self.cycles_index[now] + k) % cycle_len]
return now
#https://qiita.com/Shirotsume/items/706742162db68c481c3c
#SortedList（挿入と二分探索がΘ(logn))
class SortedList:
def __init__(self,n=20):
if not 1<=n<=20:#0~1,048,575
print('Error: not 1<=n<=20', file=sys.stderr)
sys.exit(1)
self.n=n
self.b=[]
for i in range(self.n+1):
self.b.append([0 for j in range(2**i)])
def __len__(self):
return self.b[0][0]
def __contains__(self,x):
if not 0<=x<2**self.n:
print('Error: not 0<=x<2**n', file=sys.stderr)
sys.exit(1)
return 0!=self.b[self.n][x]
def __getitem__(self,x):
if not 0<=x<self.b[0][0]:
print('Error: not 0<=x<len', file=sys.stderr)
sys.exit(1)
s=0
a=0
for i in range(1,self.n+1):
if s+self.b[i][2*a]<=x:
s+=self.b[i][2*a]
a=2*a+1
else:
a=2*a
return a
def __iter__(self):
self._a=-1
return self
def __next__(self):
self._a+=1
if self._a>=self.b[0][0]:
raise StopIteration
return self.__getitem__(self._a)
def insert(self,x):
if not 0<=x<2**self.n:
print('Error: not 0<=x<2**n', file=sys.stderr)
sys.exit(1)
for i in range(self.n+1):
self.b[i][x//(2**(self.n-i))]+=1
def eject(self,x):
if not 0<=x<2**self.n:
print('Error: not 0<=x<2**n', file=sys.stderr)
sys.exit(1)
if not self.__contains__(x):
print('Error: not x in', file=sys.stderr)
sys.exit(1)
for i in range(self.n+1):
self.b[i][x//(2**(self.n-i))]-=1
def pop(self,x=0):
p=self.__getitem__(x)
self.eject(p)
return p
def remove(self,x):
a=self.b[self.n][x]
for i in range(self.n+1):
self.b[i][x//(2**(self.n-i))]-=a
def min(self,x=None):
if x==None:
x=-1
elif x>=2**self.n-1:
return None
elif x<0:
x=-1
for i in range(self.n):
if self.b[self.n-i][x//(2**i)+1]:
a=x//(2**i)+1
for j in reversed(range(i)):
if self.b[self.n-j][2*a]:
a=2*a
else:
a=2*a+1
return a
def max(self,x=None):
if x==None:
x=2**self.n
elif x<=0:
return None
elif 2**self.n<=x:
x=2**self.n
for i in range(self.n):
if self.b[self.n-i][x//(2**i)-1]:
a=x//(2**i)-1
for j in reversed(range(i)):
if self.b[self.n-j][2*a+1]:
a=2*a+1
else:
a=2*a
return a
def bisect_left(self,x):
if not 0<=x<2**self.n:
print('Error: not 0<=x<2**n', file=sys.stderr)
sys.exit(1)
a=0
for i in range(self.n):
if x%2==1:
a+=self.b[self.n-i][x-1]
x=x//2
return a
def bisect_right(self,x):
if not 0<=x<2**self.n:
print('Error: not 0<=x<2**n', file=sys.stderr)
sys.exit(1)
return self.bisect_left(x)+self.b[self.n][x]
#SortedSet
import math
from bisect import bisect_left, bisect_right
from typing import Generic, Iterable, Iterator, TypeVar
T = TypeVar('T')
class SortedSet(Generic[T]):
BUCKET_RATIO = 16
SPLIT_RATIO = 24
def __init__(self, a: Iterable[T] = []) -> None:
"Make a new SortedSet from iterable. / O(N) if sorted and unique / O(N log N)"
a = list(a)
n = len(a)
if any(a[i] > a[i + 1] for i in range(n - 1)):
a.sort()
if any(a[i] >= a[i + 1] for i in range(n - 1)):
a, b = [], a
for x in b:
if not a or a[-1] != x:
a.append(x)
n = self.size = len(a)
num_bucket = int(math.ceil(math.sqrt(n / self.BUCKET_RATIO)))
self.a = [a[n * i // num_bucket : n * (i + 1) // num_bucket] for i in range(num_bucket)]
def __iter__(self) -> Iterator[T]:
for i in self.a:
for j in i: yield j
def __reversed__(self) -> Iterator[T]:
for i in reversed(self.a):
for j in reversed(i): yield j
def __eq__(self, other) -> bool:
return list(self) == list(other)
def __len__(self) -> int:
return self.size
def __repr__(self) -> str:
return "SortedSet" + str(self.a)
def __str__(self) -> str:
s = str(list(self))
return "{" + s[1 : len(s) - 1] + "}"
def _position(self, x: T) -> tuple[list[T], int, int]:
"return the bucket, index of the bucket and position in which x should be. self must not be empty."
for i, a in enumerate(self.a):
if x <= a[-1]: break
return (a, i, bisect_left(a, x))
def __contains__(self, x: T) -> bool:
if self.size == 0: return False
a, _, i = self._position(x)
return i != len(a) and a[i] == x
def add(self, x: T) -> bool:
"Add an element and return True if added. / O(√N)"
if self.size == 0:
self.a = [[x]]
self.size = 1
return True
a, b, i = self._position(x)
if i != len(a) and a[i] == x: return False
a.insert(i, x)
self.size += 1
if len(a) > len(self.a) * self.SPLIT_RATIO:
mid = len(a) >> 1
self.a[b:b+1] = [a[:mid], a[mid:]]
return True
def _pop(self, a: list[T], b: int, i: int) -> T:
ans = a.pop(i)
self.size -= 1
if not a: del self.a[b]
return ans
def discard(self, x: T) -> bool:
"Remove an element and return True if removed. / O(√N)"
if self.size == 0: return False
a, b, i = self._position(x)
if i == len(a) or a[i] != x: return False
self._pop(a, b, i)
return True
def lt(self, x: T) -> T | None:
"Find the largest element < x, or None if it doesn't exist."
for a in reversed(self.a):
if a[0] < x:
return a[bisect_left(a, x) - 1]
def le(self, x: T) -> T | None:
"Find the largest element <= x, or None if it doesn't exist."
for a in reversed(self.a):
if a[0] <= x:
return a[bisect_right(a, x) - 1]
def gt(self, x: T) -> T | None:
"Find the smallest element > x, or None if it doesn't exist."
for a in self.a:
if a[-1] > x:
return a[bisect_right(a, x)]
def ge(self, x: T) -> T | None:
"Find the smallest element >= x, or None if it doesn't exist."
for a in self.a:
if a[-1] >= x:
return a[bisect_left(a, x)]
def __getitem__(self, i: int) -> T:
"Return the i-th element."
if i < 0:
for a in reversed(self.a):
i += len(a)
if i >= 0: return a[i]
else:
for a in self.a:
if i < len(a): return a[i]
i -= len(a)
raise IndexError
def pop(self, i: int = -1) -> T:
"Pop and return the i-th element."
if i < 0:
for b, a in enumerate(reversed(self.a)):
i += len(a)
if i >= 0: return self._pop(a, ~b, i)
else:
for b, a in enumerate(self.a):
if i < len(a): return self._pop(a, b, i)
i -= len(a)
raise IndexError
def index(self, x: T) -> int:
"Count the number of elements < x."
ans = 0
for a in self.a:
if a[-1] >= x:
return ans + bisect_left(a, x)
ans += len(a)
return ans
def index_right(self, x: T) -> int:
"Count the number of elements <= x."
ans = 0
for a in self.a:
if a[-1] > x:
return ans + bisect_right(a, x)
ans += len(a)
return ans
#LCA(!!!sysで再帰上限を上げるように!!!)
import sys
sys.setrecursionlimit(6*10**5)
class LCAFinder:
def __init__(self, graph, root):
self.n = len(graph)
self.log = (self.n - 1).bit_length()
self.parent = [[-1] * self.log for _ in range(self.n)]
self.depth = [-1] * self.n
# 木の深さと1つ上の親をDFSで計算
self.dfs(graph, root, -1, 0)
# 倍増テーブルを構築
for j in range(1, self.log):
for i in range(self.n):
if self.parent[i][j - 1] != -1:
self.parent[i][j] = self.parent[self.parent[i][j - 1]][j - 1]
def dfs(self, graph, node, parent, depth):
self.parent[node][0] = parent # 1つ上の親
self.depth[node] = depth
for child in graph[node]:
if child != parent: # 再訪防止
self.dfs(graph, child, node, depth + 1)
def lca(self, u, v):
# 深さを同じにする
if self.depth[u] < self.depth[v]:
u, v = v, u
diff = self.depth[u] - self.depth[v]
for i in range(self.log):
if diff & (1 << i):
u = self.parent[u][i]
# 同じノードになれば終了
if u == v:
return u
# 上から二分探索で LCA を探す
for i in range(self.log - 1, -1, -1):
if self.parent[u][i] != self.parent[v][i]:
u = self.parent[u][i]
v = self.parent[v][i]
return self.parent[u][0]
#FFT（畳み込み）
class FFT():
def primitive_root_constexpr(self, m):
if m == 2: return 1
if m == 167772161: return 3
if m == 469762049: return 3
if m == 754974721: return 11
if m == 998244353: return 3
divs = [0] * 20
divs[0] = 2
cnt = 1
x = (m - 1) // 2
while (x % 2 == 0): x //= 2
i = 3
while (i * i <= x):
if (x % i == 0):
divs[cnt] = i
cnt += 1
while (x % i == 0):
x //= i
i += 2
if x > 1:
divs[cnt] = x
cnt += 1
g = 2
while (1):
ok = True
for i in range(cnt):
if pow(g, (m - 1) // divs[i], m) == 1:
ok = False
break
if ok:
return g
g += 1
def bsf(self, x):
res = 0
while (x % 2 == 0):
res += 1
x //= 2
return res
rank2 = 0
root = []
iroot = []
rate2 = []
irate2 = []
rate3 = []
irate3 = []
def __init__(self, MOD):
self.mod = MOD
self.g = self.primitive_root_constexpr(self.mod)
self.rank2 = self.bsf(self.mod - 1)
self.root = [0 for i in range(self.rank2 + 1)]
self.iroot = [0 for i in range(self.rank2 + 1)]
self.rate2 = [0 for i in range(self.rank2)]
self.irate2 = [0 for i in range(self.rank2)]
self.rate3 = [0 for i in range(self.rank2 - 1)]
self.irate3 = [0 for i in range(self.rank2 - 1)]
self.root[self.rank2] = pow(self.g, (self.mod - 1) >> self.rank2,
self.mod)
self.iroot[self.rank2] = pow(self.root[self.rank2], self.mod - 2,
self.mod)
for i in range(self.rank2 - 1, -1, -1):
self.root[i] = (self.root[i + 1] ** 2) % self.mod
self.iroot[i] = (self.iroot[i + 1] ** 2) % self.mod
prod = 1;
iprod = 1
for i in range(self.rank2 - 1):
self.rate2[i] = (self.root[i + 2] * prod) % self.mod
self.irate2[i] = (self.iroot[i + 2] * iprod) % self.mod
prod = (prod * self.iroot[i + 2]) % self.mod
iprod = (iprod * self.root[i + 2]) % self.mod
prod = 1;
iprod = 1
for i in range(self.rank2 - 2):
self.rate3[i] = (self.root[i + 3] * prod) % self.mod
self.irate3[i] = (self.iroot[i + 3] * iprod) % self.mod
prod = (prod * self.iroot[i + 3]) % self.mod
iprod = (iprod * self.root[i + 3]) % self.mod
def butterfly(self, a):
n = len(a)
h = (n - 1).bit_length()
LEN = 0
while (LEN < h):
if (h - LEN == 1):
p = 1 << (h - LEN - 1)
rot = 1
for s in range(1 << LEN):
offset = s << (h - LEN)
for i in range(p):
l = a[i + offset]
r = a[i + offset + p] * rot
a[i + offset] = (l + r) % self.mod
a[i + offset + p] = (l - r) % self.mod
rot *= self.rate2[(~s & -~s).bit_length() - 1]
rot %= self.mod
LEN += 1
else:
p = 1 << (h - LEN - 2)
rot = 1
imag = self.root[2]
for s in range(1 << LEN):
rot2 = (rot * rot) % self.mod
rot3 = (rot2 * rot) % self.mod
offset = s << (h - LEN)
for i in range(p):
a0 = a[i + offset]
a1 = a[i + offset + p] * rot
a2 = a[i + offset + 2 * p] * rot2
a3 = a[i + offset + 3 * p] * rot3
a1na3imag = (a1 - a3) % self.mod * imag
a[i + offset] = (a0 + a2 + a1 + a3) % self.mod
a[i + offset + p] = (a0 + a2 - a1 - a3) % self.mod
a[i + offset + 2 * p] = (
a0 - a2 + a1na3imag) % self.mod
a[i + offset + 3 * p] = (
a0 - a2 - a1na3imag) % self.mod
rot *= self.rate3[(~s & -~s).bit_length() - 1]
rot %= self.mod
LEN += 2
def butterfly_inv(self, a):
n = len(a)
h = (n - 1).bit_length()
LEN = h
while (LEN):
if (LEN == 1):
p = 1 << (h - LEN)
irot = 1
for s in range(1 << (LEN - 1)):
offset = s << (h - LEN + 1)
for i in range(p):
l = a[i + offset]
r = a[i + offset + p]
a[i + offset] = (l + r) % self.mod
a[i + offset + p] = (l - r) * irot % self.mod
irot *= self.irate2[(~s & -~s).bit_length() - 1]
irot %= self.mod
LEN -= 1
else:
p = 1 << (h - LEN)
irot = 1
iimag = self.iroot[2]
for s in range(1 << (LEN - 2)):
irot2 = (irot * irot) % self.mod
irot3 = (irot * irot2) % self.mod
offset = s << (h - LEN + 2)
for i in range(p):
a0 = a[i + offset]
a1 = a[i + offset + p]
a2 = a[i + offset + 2 * p]
a3 = a[i + offset + 3 * p]
a2na3iimag = (a2 - a3) * iimag % self.mod
a[i + offset] = (a0 + a1 + a2 + a3) % self.mod
a[i + offset + p] = (
a0 - a1 + a2na3iimag) * irot % self.mod
a[i + offset + 2 * p] = (
a0 + a1 - a2 - a3) * irot2 % self.mod
a[i + offset + 3 * p] = (
a0 - a1 - a2na3iimag) * irot3 % self.mod
irot *= self.irate3[(~s & -~s).bit_length() - 1]
irot %= self.mod
LEN -= 2
def convolution(self, a, b):
n = len(a);
m = len(b)
if not (a) or not (b):
return []
if min(n, m) <= 40:
res = [0] * (n + m - 1)
for i in range(n):
for j in range(m):
res[i + j] += a[i] * b[j]
res[i + j] %= self.mod
return res
z = 1 << ((n + m - 2).bit_length())
a = a + [0] * (z - n)
b = b + [0] * (z - m)
self.butterfly(a)
self.butterfly(b)
c = [(a[i] * b[i]) % self.mod for i in range(z)]
self.butterfly_inv(c)
iz = pow(z, self.mod - 2, self.mod)
for i in range(n + m - 1):
c[i] = (c[i] * iz) % self.mod
return c[:n + m - 1]
#merge-sort-tree
'''
ある区間のある値以下の個数を求める
'''
from bisect import bisect
from heapq import merge
def construct(N, A):
N0 = 2**(N-1).bit_length()
data = [None]*(2*N0)
for i, a in enumerate(A):
data[N0-1+i] = [a]
for i in range(N, N0):
data[N0-1+i] = []
for i in range(N0-2, -1, -1):
*data[i], = merge(data[2*i+1], data[2*i+2])
return N0, data
# count elements A_i s.t. A_i <= k for i in [l, r)
def query1(N0, data, l, r, k):
L = l + N0; R = r + N0
s = 0
while L < R:
if R & 1:
R -= 1
s += bisect(data[R-1], k-1)
if L & 1:
s += bisect(data[L-1], k-1)
L += 1
L >>= 1; R >>= 1
return s
# count elements A_i s.t. a <= A_i < b for i in [l, r)
def query(N0, data, l, r, a, b):
L = l + N0; R = r + N0
s = 0
while L < R:
if R & 1:
R -= 1
s += bisect(data[R-1], b-1) - bisect(data[R-1], a-1)
if L & 1:
s += bisect(data[L-1], b-1) - bisect(data[L-1], a-1)
L += 1
L >>= 1; R >>= 1
return s
#双連結リスト
import heapq
class DoublyLinkedList:
class Node:
def __init__(self, x):
self.value = x
self.left = -1
self.right = -1
self.alive = True
def __init__(self, A):
N = len(A)
self.nodes = [self.Node(x) for x in A]
for i in range(N):
if i > 0:
self.nodes[i].left = i - 1
if i + 1 < N:
self.nodes[i].right = i + 1
def left(self, i):
return self.nodes[i].left
def right(self, i):
return self.nodes[i].right
def get(self, i):
return self.nodes[i].value
def set(self, i, x):
self.nodes[i].value = x
def erase(self, i):
L = self.nodes[i].left
R = self.nodes[i].right
if L != -1:
self.nodes[L].right = R
if R != -1:
self.nodes[R].left = L
self.nodes[i].alive = False
self.nodes[i].left = -1
self.nodes[i].right = -1
def insert(self, i, x, L, R):
self.nodes[i].value = x
self.nodes[i].left = L
self.nodes[i].right = R
self.nodes[i].alive = True
if L != -1:
self.nodes[L].right = i
if R != -1:
self.nodes[R].left = i
#Treap(区間加算、区間更新)
import random
class ImplicitTreap:
def __init__(self):
# 0 = null
self.val = [0]
self.sum = [0]
self.cnt = [0]
self.pri = [0]
self.left = [0]
self.right = [0]
# lazy add
self.lazy_add = [0]
# lazy assign
self.lazy_set = [0]
self.has_set = [False]
# lazy reverse
self.rev = [False]
self.root = 0
# =========================================================
# 基本
# =========================================================
def size(self):
"""要素数を返す。O(1)"""
return self.cnt[self.root]
# =========================================================
# ノード生成
# =========================================================
def new_node(self, x):
t = len(self.val)
self.val.append(x)
self.sum.append(x)
self.cnt.append(1)
self.pri.append(
random.randint(1, 2147483647)
)
self.left.append(0)
self.right.append(0)
self.lazy_add.append(0)
self.lazy_set.append(0)
self.has_set.append(False)
self.rev.append(False)
return t
# =========================================================
# 区間代入
#
# 部分木 t 全体を x にする
# =========================================================
def apply_set(self, t, x):
if t == 0:
return
self.val[t] = x
self.sum[t] = x * self.cnt[t]
self.lazy_add[t] = 0
self.lazy_set[t] = x
self.has_set[t] = True
# =========================================================
# 区間加算
# =========================================================
def apply_add(self, t, x):
if t == 0:
return
self.val[t] += x
self.sum[t] += x * self.cnt[t]
if self.has_set[t]:
self.lazy_set[t] += x
else:
self.lazy_add[t] += x
# =========================================================
# 区間反転
# =========================================================
def apply_reverse(self, t):
if t == 0:
return
self.left[t], self.right[t] = \
self.right[t], self.left[t]
self.rev[t] = not self.rev[t]
# =========================================================
# lazy propagation
# =========================================================
def push(self, t):
if t == 0:
return
l = self.left[t]
r = self.right[t]
if self.has_set[t]:
x = self.lazy_set[t]
self.apply_set(l, x)
self.apply_set(r, x)
self.has_set[t] = False
if self.lazy_add[t] != 0:
x = self.lazy_add[t]
self.apply_add(l, x)
self.apply_add(r, x)
self.lazy_add[t] = 0
if self.rev[t]:
self.apply_reverse(l)
self.apply_reverse(r)
self.rev[t] = False
# =========================================================
# 情報更新
# =========================================================
def update(self, t):
if t == 0:
return
l = self.left[t]
r = self.right[t]
self.cnt[t] = (
self.cnt[l]
+ 1
+ self.cnt[r]
)
self.sum[t] = (
self.sum[l]
+ self.val[t]
+ self.sum[r]
)
# =========================================================
# split
#
# [0,k) | [k,n)
# =========================================================
def split(self, t, k):
if t == 0:
return 0, 0
self.push(t)
ls = self.cnt[self.left[t]]
if k <= ls:
a, b = self.split(
self.left[t],
k
)
self.left[t] = b
self.update(t)
return a, t
else:
a, b = self.split(
self.right[t],
k - ls - 1
)
self.right[t] = a
self.update(t)
return t, b
# =========================================================
# merge
# =========================================================
def merge(self, a, b):
if a == 0:
return b
if b == 0:
return a
if self.pri[a] > self.pri[b]:
self.push(a)
self.right[a] = self.merge(
self.right[a],
b
)
self.update(a)
return a
else:
self.push(b)
self.left[b] = self.merge(
a,
self.left[b]
)
self.update(b)
return b
# =========================================================
# insert
#
# p 番目に x を挿入
# =========================================================
def insert(self, p, x):
a, b = self.split(
self.root,
p
)
t = self.new_node(x)
self.root = self.merge(
self.merge(a, t),
b
)
# =========================================================
# get
#
# p 番目の要素を取得する。削除しない。
# =========================================================
def get(self, p):
a, b = self.split(
self.root,
p
)
c, d = self.split(
b,
1
)
self.push(c)
ans = self.val[c]
self.root = self.merge(
a,
self.merge(c, d)
)
return ans
# =========================================================
# pop
#
# p 番目の要素を削除して、その値を返す。
# p=-1 なら末尾。
# =========================================================
def pop(self, p=-1):
n = self.size()
if p < 0:
p += n
a, b = self.split(
self.root,
p
)
c, d = self.split(
b,
1
)
self.push(c)
ans = self.val[c]
self.root = self.merge(
a,
d
)
return ans
# =========================================================
# erase
#
# p 番目の要素を削除する。
# =========================================================
def erase(self, p):
a, b = self.split(
self.root,
p
)
c, d = self.split(
b,
1
)
self.root = self.merge(
a,
d
)
# =========================================================
# discard
#
# p 番目の要素を削除する。
# 範囲外なら何もしない。
# =========================================================
def discard(self, p):
n = self.size()
if p < 0:
p += n
if p < 0 or p >= n:
return
a, b = self.split(
self.root,
p
)
c, d = self.split(
b,
1
)
self.root = self.merge(
a,
d
)
# =========================================================
# reverse [l,r)
# =========================================================
def reverse(self, l, r):
a, b = self.split(
self.root,
l
)
c, d = self.split(
b,
r - l
)
self.apply_reverse(c)
self.root = self.merge(
a,
self.merge(c, d)
)
# =========================================================
# 区間加算 [l,r)
#
# a[i] += x
# =========================================================
def apply(self, l, r, x):
a, b = self.split(
self.root,
l
)
c, d = self.split(
b,
r - l
)
self.apply_add(c, x)
self.root = self.merge(
a,
self.merge(c, d)
)
# =========================================================
# 区間代入 [l,r)
#
# a[i] = x
# =========================================================
def assign(self, l, r, x):
a, b = self.split(
self.root,
l
)
c, d = self.split(
b,
r - l
)
self.apply_set(c, x)
self.root = self.merge(
a,
self.merge(c, d)
)
# =========================================================
# 区間和 [l,r)
# =========================================================
def prod(self, l, r):
a, b = self.split(
self.root,
l
)
c, d = self.split(
b,
r - l
)
ans = self.sum[c]
self.root = self.merge(
a,
self.merge(c, d)
)
return ans
# =========================================================
# 配列化
# =========================================================
def to_list(self):
res = []
stack = []
t = self.root
while stack or t != 0:
while t != 0:
self.push(t)
stack.append(t)
t = self.left[t]
t = stack.pop()
res.append(self.val[t])
t = self.right[t]
return res
#Treap (区間がsortされている前提で、bisect,insortがlog_n)
import random
class Treap:
def __init__(self, arr):
# node 0 = null node
self.val = [0]
self.priority = [0]
self.left = [0]
self.right = [0]
self.size_ = [0]
self.sum_ = [0]
self.root = 0
for x in arr:
self.insert(x)
# ==========================================
# 基本
# ==========================================
def size(self):
return self.size_[self.root]
def _size(self, t):
return self.size_[t]
def _sum(self, t):
return self.sum_[t]
def _update(self, t):
self.size_[t] = (
1
+ self.size_[self.left[t]]
+ self.size_[self.right[t]]
)
self.sum_[t] = (
self.val[t]
+ self.sum_[self.left[t]]
+ self.sum_[self.right[t]]
)
# ==========================================
# node 作成
# ==========================================
def _new_node(self, x):
idx = len(self.val)
self.val.append(x)
self.priority.append(random.randint(0, 2147483647))
self.left.append(0)
self.right.append(0)
self.size_.append(1)
self.sum_.append(x)
return idx
# ==========================================
# split
#
# x 以下 | x より大きい
#
# equal が False の場合：
# x 未満 | x 以上
# ==========================================
def _split_le(self, t, x):
if t == 0:
return 0, 0
if self.val[t] <= x:
a, b = self._split_le(self.right[t], x)
self.right[t] = a
self._update(t)
return t, b
else:
a, b = self._split_le(self.left[t], x)
self.left[t] = b
self._update(t)
return a, t
def _split_lt(self, t, x):
if t == 0:
return 0, 0
if self.val[t] < x:
a, b = self._split_lt(self.right[t], x)
self.right[t] = a
self._update(t)
return t, b
else:
a, b = self._split_lt(self.left[t], x)
self.left[t] = b
self._update(t)
return a, t
# ==========================================
# merge
# ==========================================
def _merge(self, a, b):
if a == 0:
return b
if b == 0:
return a
if self.priority[a] > self.priority[b]:
self.right[a] = self._merge(
self.right[a],
b
)
self._update(a)
return a
else:
self.left[b] = self._merge(
a,
self.left[b]
)
self._update(b)
return b
# ==========================================
# insert
# ==========================================
def insert(self, x):
node = self._new_node(x)
# x 以下 | x より大きい
a, b = self._split_le(self.root, x)
self.root = self._merge(
self._merge(a, node),
b
)
# ==========================================
# bisect_left
#
# x 以上の最初の位置
#
# 例：
# [1, 2, 2, 5]
#
# bisect_left(2) = 1
# ==========================================
def bisect_left(self, x):
t = self.root
ans = 0
while t != 0:
if self.val[t] >= x:
t = self.left[t]
else:
ans += 1 + self.size_[self.left[t]]
t = self.right[t]
return ans
# ==========================================
# bisect_right
#
# x より大きい最初の位置
#
# 例：
# [1, 2, 2, 5]
#
# bisect_right(2) = 3
# ==========================================
def bisect_right(self, x):
t = self.root
ans = 0
while t != 0:
if self.val[t] > x:
t = self.left[t]
else:
ans += 1 + self.size_[self.left[t]]
t = self.right[t]
return ans
# ==========================================
# sum_prefix
#
# x 未満の要素の総和
#
# 例：
# [1, 2, 2, 5]
#
# sum_prefix(5) = 5
# ==========================================
def sum_prefix(self, x):
t = self.root
ans = 0
while t != 0:
if self.val[t] >= x:
t = self.left[t]
else:
ans += (
self.sum_[self.left[t]]
+ self.val[t]
)
t = self.right[t]
return ans
# ==========================================
# sum_prefix_right
#
# x 以下の要素の総和
# ==========================================
def sum_prefix_right(self, x):
t = self.root
ans = 0
while t != 0:
if self.val[t] > x:
t = self.left[t]
else:
ans += (
self.sum_[self.left[t]]
+ self.val[t]
)
t = self.right[t]
return ans
# ==========================================
# prod
#
# 値 l <= x < r の総和
#
# 例：
# [1, 2, 2, 4, 5, 7]
#
# prod(2, 7)
#
# = 2 + 2 + 4 + 5
# = 13
# ==========================================
def prod(self, l, r):
return (
self.sum_prefix(r)
- self.sum_prefix(l)
)
# ==========================================
# get
#
# ソート順で i 番目の値
# ==========================================
def get(self, i):
t = self.root
while t != 0:
ls = self.size_[self.left[t]]
if i < ls:
t = self.left[t]
elif i == ls:
return self.val[t]
else:
i -= ls + 1
t = self.right[t]
return 0
# ==========================================
# erase_one
#
# x を1個削除
# ==========================================
def erase_one(self, x):
a, b = self._split_lt(self.root, x)
c, d = self._split_le(b, x)
# c の中から1個削除
# c が空なら何もしない
if c != 0:
c = self._erase_root(c)
self.root = self._merge(
a,
self._merge(c, d)
)
def _erase_root(self, t):
return self._merge(
self.left[t],
self.right[t]
)
# ==========================================
# 全要素取得
# ==========================================
def to_list(self):
res = []
stack = []
t = self.root
while stack or t != 0:
while t != 0:
stack.append(t)
t = self.left[t]
t = stack.pop()
res.append(self.val[t])
t = self.right[t]
return res
#任意のモノイドを乗せられるTreap
# =========================================================
# Implicit Treap
#
# 任意のオブジェクトを要素として持つ
#
# 例:
# ["ab", "ac", "d", "bcd"]
#
# 対応操作:
#
# insert(p, x) : p番目にxを挿入
# get(p) : p番目を取得
# pop(p) : p番目を削除して返す
# erase(p) : p番目を削除
# reverse(l, r) : [l,r) を反転
# to_list() : 全体をリストとして取得
# size() : 要素数
# build(arr) : 配列から構築
#
# insert / get / pop / erase / reverse
# 期待 O(log N)
#
# to_list
# O(N)
#
# 区間積・区間和などの情報は一切持たない
# =========================================================
import random
class ImplicitTreap:
def __init__(self):
# 0 = null
self.val = [None]
self.cnt = [0]
self.pri = [0]
self.left = [0]
self.right = [0]
# lazy reverse
self.rev = [False]
self.root = 0
# =========================================================
# size
# =========================================================
def size(self):
return self.cnt[self.root]
# =========================================================
# new node
# =========================================================
def new_node(self, x):
t = len(self.val)
self.val.append(x)
self.cnt.append(1)
self.pri.append(
random.randint(1, 2147483647)
)
self.left.append(0)
self.right.append(0)
self.rev.append(False)
return t
# =========================================================
# apply reverse
#
# 部分木全体を反転
# =========================================================
def apply_reverse(self, t):
if t == 0:
return
self.left[t], self.right[t] = \
self.right[t], self.left[t]
self.rev[t] = not self.rev[t]
# =========================================================
# push
# =========================================================
def push(self, t):
if t == 0:
return
if self.rev[t]:
self.apply_reverse(
self.left[t]
)
self.apply_reverse(
self.right[t]
)
self.rev[t] = False
# =========================================================
# update
# =========================================================
def update(self, t):
if t == 0:
return
l = self.left[t]
r = self.right[t]
self.cnt[t] = (
self.cnt[l]
+ 1
+ self.cnt[r]
)
# =========================================================
# split
#
# [0,k) | [k,n)
# =========================================================
def split(self, t, k):
if t == 0:
return 0, 0
self.push(t)
ls = self.cnt[self.left[t]]
if k <= ls:
a, b = self.split(
self.left[t],
k
)
self.left[t] = b
self.update(t)
return a, t
else:
a, b = self.split(
self.right[t],
k - ls - 1
)
self.right[t] = a
self.update(t)
return t, b
# =========================================================
# merge
# =========================================================
def merge(self, a, b):
if a == 0:
return b
if b == 0:
return a
if self.pri[a] > self.pri[b]:
self.push(a)
self.right[a] = self.merge(
self.right[a],
b
)
self.update(a)
return a
else:
self.push(b)
self.left[b] = self.merge(
a,
self.left[b]
)
self.update(b)
return b
# =========================================================
# insert
#
# p番目の前に x を挿入
#
# ["a","b","c"]
# insert(1,"X")
#
# -> ["a","X","b","c"]
# =========================================================
def insert(self, p, x):
a, b = self.split(
self.root,
p
)
t = self.new_node(x)
self.root = self.merge(
self.merge(a, t),
b
)
# =========================================================
# get
#
# p番目の要素を取得
# =========================================================
def get(self, p):
a, b = self.split(
self.root,
p
)
c, d = self.split(
b,
1
)
self.push(c)
ans = self.val[c]
self.root = self.merge(
a,
self.merge(c, d)
)
return ans
# =========================================================
# pop
#
# p番目を削除して返す
#
# p=-1 なら末尾
# =========================================================
def pop(self, p=-1):
n = self.size()
if p < 0:
p += n
a, b = self.split(
self.root,
p
)
c, d = self.split(
b,
1
)
self.push(c)
ans = self.val[c]
self.root = self.merge(
a,
d
)
return ans
# =========================================================
# erase
#
# p番目を削除
# =========================================================
def erase(self, p):
a, b = self.split(
self.root,
p
)
c, d = self.split(
b,
1
)
self.root = self.merge(
a,
d
)
# =========================================================
# reverse
#
# [l,r) を反転
# =========================================================
def reverse(self, l, r):
a, b = self.split(
self.root,
l
)
c, d = self.split(
b,
r - l
)
self.apply_reverse(c)
self.root = self.merge(
a,
self.merge(c, d)
)
# =========================================================
# to_list
# =========================================================
def to_list(self):
res = []
stack = []
t = self.root
while stack or t != 0:
while t != 0:
self.push(t)
stack.append(t)
t = self.left[t]
t = stack.pop()
res.append(
self.val[t]
)
t = self.right[t]
return res
# =========================================================
# build
#
# arr からTreapを構築
# =========================================================
def build(self, arr):
self.root = 0
for x in arr:
t = self.new_node(x)
self.root = self.merge(
self.root,
t
)