ACL Practice Contestをac-library-pythonで解いてみたよ。(G～L問題)

# はじめに
2023年8月にあった大幅なAtCoderの言語アップデートで、PythonにもACLとよばれる競プロライブラリが追加されました。

https://github.com/not522/ac-library-python/

この記事では、そのライブラリの使い方を [ACL Practice Contest](https://atcoder.jp/contests/practice2) の問題を通して見ていきます。

この記事ではG問題以降を見ていきます。A～F問題については下の記事を見てください。

https://qiita.com/hyouchun/items/4958618268407a5442cc

:::note info
ac-library-pythonの具体的な使い方が分かります。
:::
:::note warn
内部の詳細な実装は、上のGitHubを参考にしてください。
核となる問題の解き方は、ユーザー解説などを参考にしてください。
:::

# G - SCC

## 問題

https://atcoder.jp/contests/practice2/tasks/practice2_g

## 解説
強連結成分分解です。
また、問題文にはトポロジカルソートした状態で出力するように書かれていますが、ac-library-pythonの強連結成分分解はトポロジカルソートされた状態でリストを返してくれるので、今回は気にせず出力してよいです。

<details> <summary>強連結成分分解とは</summary>
有向グラフにおいて、お互いに行き来できる頂点を1つのグループにまとめることを、強連結成分分解と言います。
</details>

<details><summary>トポロジカルソートとは</summary>
頂点 $u_i$ から頂点 $v_i$ への有向辺があったとき、 $u_i$ の属する強連結成分よりも $v_i$ の属する強連結成分の方が後ろになるように並べることを、トポロジカルソートと言います。
</details>

## メソッド一覧
- `graph = SCCGraph(N)` : 頂点数 $N$ のグラフをつくる。
- `graph.add_edge(u, v)` : 頂点 $u$ から頂点 $v$ への有向辺をはる。
- `graph.scc()` : 2次元リストを返す。各要素(リスト)は強連結成分です。またトポロジカルソートされていて、異なる強連結成分の頂点 $u, v$ について $u$ から $v$ に到達できるとき、 $u$ の属するリストは $v$ の属するリストよりも前にある。

## コード
```Python
from atcoder.scc import SCCGraph

N, M = map(int, input().split())
graph = SCCGraph(N)
for _ in range(M):
    a, b = map(int, input().split())
    graph.add_edge(a, b)

groups = graph.scc()
print(len(groups))
for group in groups:
    print(len(group), *group)
```

# H - Two SAT

## 問題

https://atcoder.jp/contests/practice2/tasks/practice2_h

## 解説
Two SAT 問題を解きます。
Two SAT 問題とは、$(a \lor b) \land (c \lor d) \land (e \lor f) \land \cdots$ の式があったときに、$a, b, c, \cdots $ に対して適切に真偽値(True か False) を当てはめることで、式全体をTrueにできるかどうか、という問題のことです。

旗 $i$ を座標 $X_i$ に設置することを True、座標 $Y_i$ に設置することをFalseとします。
たとえば $2$ つの旗 $i, j$ について $|X_i-X_j|<D$ だったとき、旗 $i, j$ をそれぞれ $X_i, X_j$ に置くことはできず、「旗 $i$ を 座標 $Y_i$ に置く」または「旗 $j$ を座標 $Y_j$ に置く」のどちらかを満たさないといけません。つまり、 $i=\text{False} \lor j=\text{False}$ が成り立ちます。
これをそれぞれの旗・座標に対しておこないます。

## メソッド一覧
- `twosat = TwoSAT(N)` : $N$ 変数の Two SAT をつくる。
- `twosat.add_clause(i, f, j, g)` : $(x_i = f) \lor (x_j = g)$ の条件式を追加する。
- `twosat.satisfiable()` : 条件を満たすように $x_1, x_2, \cdots ,x_N$ に真偽値を割り当てられるならTrueを、そうでなければFalseを返す。
- `twosat.answer()` : 最後に呼んだ`satisfiable()` のときの  $x_1, x_2, \cdots ,x_N$ の真偽値リストを返す。

## コード
```Python
from atcoder.twosat import TwoSAT

N, D = map(int, input().split())
Flag = [tuple(map(int, input().split())) for _ in range(N)]

twosat = TwoSAT(N)

for i in range(N - 1):
    for j in range(i + 1, N):
        if i == j:
            continue
        if abs(Flag[i][0] - Flag[j][0]) < D:
            twosat.add_clause(i, False, j, False)
        if abs(Flag[i][0] - Flag[j][1]) < D:
            twosat.add_clause(i, False, j, True)
        if abs(Flag[i][1] - Flag[j][0]) < D:
            twosat.add_clause(i, True, j, False)
        if abs(Flag[i][1] - Flag[j][1]) < D:
            twosat.add_clause(i, True, j, True)

if twosat.satisfiable():
    print("Yes")
    ans = twosat.answer()
    for i in range(N):
        if ans[i]:
            print(Flag[i][0])
        else:
            print(Flag[i][1])
else:
    print("No")
```

# I - Number of Substrings

## 問題

https://atcoder.jp/contests/practice2/tasks/practice2_i

## 解説
連続する部分文字列の種類数を求めます。

しかし部分文字列の種類数を求めるものはac-library-pythonにはありません。
その代わりにac-library-pythonの中にあるsuffix-arrayとlcp-arrayをつかうことで、この問題を解くことができます。

<details><summary>suffix-arrayとは。</summary>
<dl>

<dt>suffix-arrayとは。</dt>

<dd>和訳すると、「接尾辞配列」です。<br>たとえば文字列 $S$ が "abcbc" だったとします。<br> $i=0, 1, \cdots , |S|-1$ について、$S[i:]$ をリスト $P$ に入れます。すなわち、 $P$ の中には、 "abcbc", "bcbc", "cbc", "bc", "c" の $5$ つが入っていることになります。<br>
これを辞書順にソートします。すなわち、 $P$ は左から順に、 "abcbc", "bc", "bcbc", "c", "cbc" になります。<br>
それぞれの文字列について、ソートする前の $P$ でのインデックスに置き換えます。つまり、 $[0,3,1,4,2]$ になります。このリストがsuffix-arrayです。</dd>
</dl>
</details>

<details><summary>suffix-arrayの大まかな解説コード</summary>

上の文字解説をコードに書き起こしました。<br>
実際に内部で実装されているアルゴリズムの方が高速で、これは雰囲気をつかむためだけのものなので注意してください。

```Python
"""ac-library-pythonの内部実装とは違うのに注意してね。"""

S = "abcbc"
P = [S[i:] for i in range(len(S))]
sP = sorted(P)
suffix_array = [P.index(ele) for ele in sP]
```

</details>


<details><summary>lcp-arrayとは。</summary>
<dl>
<dt>lcp-arrayとは。</dt>

<dd>LCPはLongest Common Prefixの略で、和訳すると「最長共通接頭辞」です。<br>先ほどのsuffix-arrayで、 $i=0, 1, \cdots , |S|-1$ に対して $S[i:]$ を辞書順に管理できました。<br>
lcp-arrayでは、各 $i$ についてその辞書順の $i$ 番目と $i+1$ 番目の文字列のLCPを求めます。<br>
たとえば上のsuffix-arrayで用いた文字列 $S=\text{abcbc}$ について、suffix-arrayで辞書順に並べた結果、 $1$ 番目と $2$ 番目はそれぞれ "bc" と "bcbc" でした。この2つは "bc" の部分が接頭辞として共通しているのでLCPは $2$ です。<br>同様にして他のLCPも求めると、 $[0,2,0,1]$ になります。これがlcp-arrayです。
</dd>

</dl>
</details>

<details><summary>lcp-arrayの大まかな解説コード</summary>
上の文字解説をコードに書き起こしました。<br>
実際に内部で実装されているアルゴリズムの方が高速で、これは雰囲気をつかむためだけのものなので注意してください。

```Python
"""ac-library-pythonの内部実装とは違うのに注意してね。"""

def lcp(s1, s2):
    result = 0
    for el1, el2 in zip(s1, s2):
        if el1 == el2:
            result += 1
        else:
            break
    return result


S = "abcbc"
P = [S[i:] for i in range(len(S))]
P.sort()
lcp_array = [lcp(P[i], P[i + 1]) for i in range(len(P) - 1)]
```

</details>




## メソッド一覧
- `sa = suffix_array(S)` : 文字列 $S$ のsuffix-arrayとして、長さ $|S|$ のリストを返す。
- `la = lcp_array(S, sa)` : 文字列 $S$ のLCP-array として、長さ $|S|-1$ のリストを返す。
- `z = z_algorithm(S)` : 長さ $|S|$ のリストを返す。 $i$ 番目の要素は、 $S$ と $S[i:]$ のLCP(最長共通接頭辞)の長さ。
## コード
```Python
from atcoder.string import suffix_array, lcp_array

S = input()
sa = suffix_array(S)

ans = len(S) * (len(S) + 1) // 2
for x in lcp_array(S, sa):
    ans -= x
print(ans)
```

# J- Segment Tree

## 問題

https://atcoder.jp/contests/practice2/tasks/practice2_j

## 解説
セグメントツリーです。
- リスト内のインデックスを $1$ つ指定して、そのインデックスの値を変更する。
- リスト内の範囲を指定して、その区間全体に対する演算(総和 $\text{sum}$ や最小値 $\min$ など)を行った結果を取得する。

の $2$ つをどちらも $O(\log N)$ で行えます。

## メソッド一覧
- `st = SegTree(op, e, v)` : セグメントツリーを構築する。$op$ は区間の演算につかう関数、$e$ はその単位元。 $v$ にはlist型かint型を入れる。list型の場合はそのリストをそのまま入り、int型の場合はすべての要素が単位元 $e$ で長さ $v$ のリストになる。 
- `st.set(p, x)` : リスト $A$ について、$A_p$ に $x$ を代入する。 
- `st.get(p)` : リスト $A$ の $p$ 番目の要素 $A_p$ を返す。
- `st.prod(l, r)` : 半開区間 $[l: r)$ における演算の結果を返す。
- `st.all_prod()` : リスト全体における演算の結果を返す。 
- `st.max_right(p, func)` : セグメントツリー上で二分探索をする。 $p \leq i$ を満たす $i$ の中で、関数 $\text{func}$ を満たす最小の $i$ を返す。 
- `st.min_left(p, func)` : セグメントツリー上で二分探索をする。 $i < p$ を満たす $i$ の中で、関数 $\text{func}$ を満たす最大の $i$ を返す。 

## コード
```Python
from atcoder.segtree import SegTree

N, Q = map(int, input().split())
A = list(map(int, input().split()))

st = SegTree(max, -1, A)

for _ in range(Q):
    t, x, y = map(int, input().split())
    if t == 1:
        st.set(x - 1, y)
    elif t == 2:
        print(st.prod(x - 1, y))
    else:
        print(st.max_right(x - 1, lambda p: p < y) + 1)
```

# K - Range Affine Range Sum

## 問題

https://atcoder.jp/contests/practice2/tasks/practice2_k

## 解説
遅延セグメントツリーです。

- リスト内の範囲を指定して、その値を一括で変更する。
- リスト内の範囲を指定して、その区間全体に対する演算(総和 $\text{sum}$ や最小値 $\min$ など)を行った結果を取得する。

の $2$ つをどちらも $O(\log N)$ で行えます。

この問題では、モノイドとして遅延セグメントツリーに (値, そのノードの区間の長さ) のタプルをのせています。

## 解説記事
- [Pythonで遅延セグメントツリーの問題を解けるようにする！](https://qiita.com/hyouchun/items/1748bd320d2188a999f2) (私の記事です。)

- [AtCoder LibraryのLazy Segtreeの使い方](https://betrue12.hateblo.jp/entry/2020/09/22/194541) (アルメリアさんの記事です。)

## メソッド一覧
- `ls = LazySegTree(op, e, mapping, composition, _id, lst)` : 遅延セグメントツリーを構築する。引数は以下の通り。
    - `op` : 区間取得の演算
    - `e` : $op$ の単位元
    -  `mapping` :  $\text{data}$ に $\text{lazy}$ を作用させたときの関数
    -  `composition` : $\text{lazy}$ に別の $\text{lazy}$ を作用させたときの関数
    -  `_id` : $\text{mapping}$ の恒等写像、
    -  `lst` : 初期リスト。
- `ls.apply(l, r , f)` リスト $A$ について、 $i=l,l+1, \cdots , r-1$ それぞれに対して $A_i$ に $f$ を作用させる。
- `ls.set(p, x)` リスト $A$ について、 $A_p$ に $x$ を代入する。
- `ls.get(p)` : リスト $A$ の $p$ 番目の要素 $A_p$ を返す。
- `ls.prod(l, r)` : 半開区間 $[l: r)$ における演算の結果を返す。
- `ls.all_prod()` : リスト全体における演算の結果を返す。 
- `ls.max_right(p, func)` : セグメントツリー上で二分探索をする。 $p \leq i$ を満たす $i$ の中で、関数 $\text{func}$ を満たす最小の $i$ を返す。 
- `ls.min_left(p, func)` : セグメントツリー上で二分探索をする。 $i < p$ を満たす $i$ の中で、関数 $\text{func}$ を満たす最大の $i$ を返す。 

## コード
```Python
from atcoder.lazysegtree import LazySegTree

MOD = 998244353

e = (0, 0)  # opの単位元 (値, このノードの区間の長さ)
_id = (1, 0)  # mappingにおける恒等写像

# 区間取得の演算
def op(data1, data2):
    sum1, length1 = data1
    sum2, length2 = data2
    next_sum = (sum1 + sum2) % MOD
    next_length = length1 + length2
    return next_sum, next_length

# lazy -> data
def mapping(lazy_upper, data_lower):
    b, c = lazy_upper
    sum1, length1 = data_lower
    next_sum = (b * sum1 + c * length1) % MOD
    return next_sum, length1

# lazy -> lazy
def composition(lazy_upper, lazy_lower):
    b2, c2 = lazy_upper
    b1, c1 = lazy_lower
    next_b = b1 * b2 % MOD
    next_c = (b2 * c1 + c2) % MOD
    return next_b, next_c


N, Q = map(int, input().split())
A = list(map(int, input().split()))

lst = [(a, 1) for a in A]

ls = LazySegTree(op, e, mapping, composition, _id, lst)

for _ in range(Q):
    t, *q = map(int, input().split())
    if t == 0:
        l, r, b, c = q
        ls.apply(l, r, (b, c))
    else:
        l, r = q
        ans = ls.prod(l, r)[0]
        print(ans)
```

# L - Lazy Segment Tree

## 問題

https://atcoder.jp/contests/practice2/tasks/practice2_l

## 解説
遅延セグメントツリーです。
K問題とつかうデータ構造は同じです。
この問題では、モノイドとして遅延セグメントツリーに (0の個数, 1の個数, ノード内での転倒数)　のタプルをのせています。

## メソッド一覧
(K問題と同じなので省略)

## コード
```Python
from atcoder.lazysegtree import LazySegTree

e = (0, 0, 0)  # opの単位元 (0の個数, 1の個数, このノード内での転倒数)
_id = False  # mappingにおける恒等写像


# 区間取得の演算
def op(ele1, ele2):
    l0, l1, l_inv = ele1
    r0, r1, r_inv = ele2
    nex0 = l0 + r0
    nex1 = l1 + r1
    nex_inv = l_inv + r_inv + l1 * r0
    return nex0, nex1, nex_inv


# lazy -> data
def mapping(func, ele):
    x0, x1, x_inv = ele
    if func:
        return x1, x0, x0 * x1 - x_inv
    else:
        return x0, x1, x_inv


# lazy -> lazy
def composition(func_upper, func_lower):
    if func_upper:
        return not func_lower
    else:
        return func_lower


N, Q = map(int, input().split())
A = list(map(int, input().split()))

lst = [(0, 1, 0) if a == 1 else (1, 0, 0) for a in A]
lazy_segtree = LazySegTree(op, e, mapping, composition, _id, lst)

for _ in range(Q):
    t, l, r = map(int, input().split())
    if t == 1:
        lazy_segtree.apply(l - 1, r, True)
    else:
        print(lazy_segtree.prod(l - 1, r)[2])
```