1# from titan_pylib.string.string_count import StringCount
2# from titan_pylib.data_structures.fenwick_tree.fenwick_tree import FenwickTree
3from typing import Union, Iterable, Optional
4
5
6class FenwickTree:
7 """FenwickTreeです。"""
8
9 def __init__(self, n_or_a: Union[Iterable[int], int]):
10 """構築します。
11 :math:`O(n)` です。
12
13 Args:
14 n_or_a (Union[Iterable[int], int]): `n_or_a` が `int` のとき、初期値 `0` 、長さ `n` で構築します。
15 `n_or_a` が `Iterable` のとき、初期値 `a` で構築します。
16 """
17 if isinstance(n_or_a, int):
18 self._size = n_or_a
19 self._tree = [0] * (self._size + 1)
20 else:
21 a = n_or_a if isinstance(n_or_a, list) else list(n_or_a)
22 _size = len(a)
23 _tree = [0] + a
24 for i in range(1, _size):
25 if i + (i & -i) <= _size:
26 _tree[i + (i & -i)] += _tree[i]
27 self._size = _size
28 self._tree = _tree
29 self._s = 1 << (self._size - 1).bit_length()
30
31 def pref(self, r: int) -> int:
32 """区間 ``[0, r)`` の総和を返します。
33 :math:`O(\\log{n})` です。
34 """
35 assert (
36 0 <= r <= self._size
37 ), f"IndexError: {self.__class__.__name__}.pref({r}), n={self._size}"
38 ret, _tree = 0, self._tree
39 while r > 0:
40 ret += _tree[r]
41 r &= r - 1
42 return ret
43
44 def suff(self, l: int) -> int:
45 """区間 ``[l, n)`` の総和を返します。
46 :math:`O(\\log{n})` です。
47 """
48 assert (
49 0 <= l < self._size
50 ), f"IndexError: {self.__class__.__name__}.suff({l}), n={self._size}"
51 return self.pref(self._size) - self.pref(l)
52
53 def sum(self, l: int, r: int) -> int:
54 """区間 ``[l, r)`` の総和を返します。
55 :math:`O(\\log{n})` です。
56 """
57 assert (
58 0 <= l <= r <= self._size
59 ), f"IndexError: {self.__class__.__name__}.sum({l}, {r}), n={self._size}"
60 _tree = self._tree
61 res = 0
62 while r > l:
63 res += _tree[r]
64 r &= r - 1
65 while l > r:
66 res -= _tree[l]
67 l &= l - 1
68 return res
69
70 prod = sum
71
72 def __getitem__(self, k: int) -> int:
73 """位置 ``k`` の要素を返します。
74 :math:`O(\\log{n})` です。
75 """
76 assert (
77 -self._size <= k < self._size
78 ), f"IndexError: {self.__class__.__name__}[{k}], n={self._size}"
79 if k < 0:
80 k += self._size
81 return self.sum(k, k + 1)
82
83 def add(self, k: int, x: int) -> None:
84 """``k`` 番目の値に ``x`` を加えます。
85 :math:`O(\\log{n})` です。
86 """
87 assert (
88 0 <= k < self._size
89 ), f"IndexError: {self.__class__.__name__}.add({k}, {x}), n={self._size}"
90 k += 1
91 _tree = self._tree
92 while k <= self._size:
93 _tree[k] += x
94 k += k & -k
95
96 def __setitem__(self, k: int, x: int):
97 """``k`` 番目の値を ``x`` に更新します。
98 :math:`O(\\log{n})` です。
99 """
100 assert (
101 -self._size <= k < self._size
102 ), f"IndexError: {self.__class__.__name__}[{k}] = {x}, n={self._size}"
103 if k < 0:
104 k += self._size
105 pre = self[k]
106 self.add(k, x - pre)
107
108 def bisect_left(self, w: int) -> Optional[int]:
109 i, s, _size, _tree = 0, self._s, self._size, self._tree
110 while s:
111 if i + s <= _size and _tree[i + s] < w:
112 w -= _tree[i + s]
113 i += s
114 s >>= 1
115 return i if w else None
116
117 def bisect_right(self, w: int) -> int:
118 i, s, _size, _tree = 0, self._s, self._size, self._tree
119 while s:
120 if i + s <= _size and _tree[i + s] <= w:
121 w -= _tree[i + s]
122 i += s
123 s >>= 1
124 return i
125
126 def _pop(self, k: int) -> int:
127 assert k >= 0
128 i, acc, s, _size, _tree = 0, 0, self._s, self._size, self._tree
129 while s:
130 if i + s <= _size:
131 if acc + _tree[i + s] <= k:
132 acc += _tree[i + s]
133 i += s
134 else:
135 _tree[i + s] -= 1
136 s >>= 1
137 return i
138
139 def tolist(self) -> list[int]:
140 """リストにして返します。
141 :math:`O(n)` です。
142 """
143 sub = [self.pref(i) for i in range(self._size + 1)]
144 return [sub[i + 1] - sub[i] for i in range(self._size)]
145
146 @staticmethod
147 def get_inversion_num(a: list[int], compress: bool = False) -> int:
148 inv = 0
149 if compress:
150 a_ = sorted(set(a))
151 z = {e: i for i, e in enumerate(a_)}
152 fw = FenwickTree(len(a_) + 1)
153 for i, e in enumerate(a):
154 inv += i - fw.pref(z[e] + 1)
155 fw.add(z[e], 1)
156 else:
157 fw = FenwickTree(len(a) + 1)
158 for i, e in enumerate(a):
159 inv += i - fw.pref(e + 1)
160 fw.add(e, 1)
161 return inv
162
163 def __str__(self):
164 return str(self.tolist())
165
166 def __repr__(self):
167 return f"{self.__class__.__name__}({self})"
168import string
169
170
171class StringCount:
172
173 def __init__(self, s: str, is_lower: bool = True):
174 assert isinstance(s, str)
175 self.alp: str = string.ascii_lowercase if is_lower else string.ascii_uppercase
176 self.DIC: dict[str, int] = {c: i for i, c in enumerate(self.alp)}
177 self.n: int = len(s)
178 self.s: list[str] = list(s)
179 dat: list[list[int]] = [[0] * self.n for _ in range(26)]
180 for i, c in enumerate(s):
181 dat[self.DIC[c]][i] += 1
182 self.data: list[FenwickTree] = [FenwickTree(d) for d in dat]
183
184 def is_ascending(self, l: int, r: int) -> bool:
185 """区間[l, r)が昇順かどうか判定する / O(σlogn)"""
186 assert 0 <= l <= r <= self.n
187 end = l
188 for dat in self.data:
189 c = dat.sum(l, r)
190 end += c
191 if end > r or dat.sum(l, end) != c:
192 return False
193 return True
194
195 def is_descending(self, l: int, r: int) -> bool:
196 """
197 区間[l, r)が降順かどうか判定する / O(σlogn)
198 Note: 未確認
199 """
200 assert 0 <= l <= r <= self.n
201 start = r - 1
202 for dat in reversed(self.data):
203 c = dat.sum(l, r)
204 start -= c
205 if start < l or dat.sum(start, r) != c:
206 return False
207 return True
208
209 def get_min(self, l: int, r: int) -> str:
210 """区間[l, r)の最小の文字を返す / O(σlogn)"""
211 for i in range(26):
212 if self.data[i].sum(l, r):
213 return self.alp[i]
214 assert False, "Indexerror"
215
216 def get_max(self, l: int, r: int) -> str:
217 """区間[l, r)の最大の文字を返す / O(σlogn)"""
218 for i in range(25, -1, -1):
219 if self.data[i].sum(l, r):
220 return self.alp[i]
221 assert False, "Indexerror"
222
223 def __setitem__(self, k: int, c: str):
224 """k番目の文字をcに変更する / O(logn)"""
225 assert 0 <= k < self.n
226 self.data[self.DIC[self.s[k]]].add(k, -1)
227 self.s[k] = c
228 self.data[self.DIC[c]].add(k, 1)
229
230 # 区間[l, r)の全ての文字の個数を返す
231 # 返り値は要素数26のlist[int]
232 def get_all_count(self, l: int, r: int) -> list[int]:
233 return [self.data[i].sum(l, r) for i in range(26)]
234
235 def get_count(self, l: int, r: int, c: str) -> int:
236 """区間[l, r)のcの個数を返す / O(logn)"""
237 return self.data[self.DIC[c]].sum(l, r)
238
239 def __getitem__(self, k: int) -> str:
240 return self.s[k]
241
242 def __str__(self):
243 return "".join(self.s)