1# from titan_pylib.data_structures.deque.foldable_deque import FoldableDeque
2# from titan_pylib.data_structures.stack.foldable_stack import FoldableStack
3from typing import Generic, Iterable, TypeVar, Callable, Union
4
5T = TypeVar("T")
6
7
8class FoldableStack(Generic[T]):
9
10 def __init__(
11 self, n_or_a: Union[int, Iterable[T]], op: Callable[[T, T], T], e: T
12 ) -> None:
13 self._op = op
14 self._e = e
15 if isinstance(n_or_a, int):
16 self._n = n_or_a
17 self._a = [e] * self._n
18 else:
19 n_or_a = list(n_or_a)
20 self._n = len(n_or_a)
21 self._a = list(n_or_a)
22 self._data = [e] * (self._n + 1)
23 for i in range(self._n):
24 self._data[i + 1] = op(self._data[i], self._a[i])
25
26 def append(self, key: T) -> None:
27 self._a.append(key)
28 self._data.append(self._op(self._data[-1], key))
29
30 def top(self) -> T:
31 return self._a[-1]
32
33 def pop(self) -> T:
34 self._data.pop()
35 return self._a.pop()
36
37 def all_prod(self) -> T:
38 return self._data[-1]
39
40 def prod(self, r: int) -> T:
41 return self._data[r]
42
43 def tolist(self) -> list[T]:
44 return list(self._a)
45
46 def __len__(self):
47 return len(self._a)
48from typing import Generic, Iterable, TypeVar, Callable, Union
49
50T = TypeVar("T")
51
52
53class FoldableDeque(Generic[T]):
54
55 def __init__(
56 self, n_or_a: Union[int, Iterable[T]], op: Callable[[T, T], T], e: T
57 ) -> None:
58 self._op = op
59 self._e = e
60 self.front: FoldableStack[T] = FoldableStack(0, op, e)
61 self.back: FoldableStack[T] = FoldableStack(n_or_a, op, e)
62
63 def _rebuild(self) -> None:
64 new = self.front.tolist()[::-1] + self.back.tolist()
65 self.front = FoldableStack(new[: len(new) // 2][::-1], self._op, self._e)
66 self.back = FoldableStack(new[len(new) // 2 :], self._op, self._e)
67
68 def tolist(self) -> list[T]:
69 return self.front.tolist()[::-1] + self.back.tolist()
70
71 def append(self, v: T) -> None:
72 self.back.append(v)
73
74 def appendleft(self, v: T) -> None:
75 self.front.append(v)
76
77 def pop(self) -> T:
78 if not self.back:
79 self._rebuild()
80 return self.back.pop() if self.back else self.front.pop()
81
82 def popleft(self) -> T:
83 if not self.front:
84 self._rebuild()
85 return self.front.pop() if self.front else self.back.pop()
86
87 def all_prod(self) -> T:
88 return self._op(self.front.all_prod(), self.back.all_prod())
89
90 def __len__(self):
91 return len(self.front) + len(self.back)