【競技プログラミング】AtCoder Beginner Contest 380_E問題

# 問題
https://atcoder.jp/contests/abc380/tasks/abc380_e

# 既存投稿一覧ページへのリンク
[一覧ページ](https://qiita.com/o_chan_t/items/fc759695acfaef8df2cc)

## Before
[AtCoder Beginner Contest 380_D 問題](https://qiita.com/o_chan_t/items/6d516a0445d5920bd9fa)

## Next
[AtCoder Beginner Contest 381_C 問題]()

## その他・記事まとめ
[Unity関連 / Qiita](https://qiita.com/o_chan_t/items/0b5ae1e7c45f106082b8)


# 解法手順1
### データ構造の選択
**Union-Find（DSU）**
- 連結成分の高速な統合・管理が可能
- 各集合に付随情報（色・範囲）を保持可能

```python
from atcoder.dsu import DSU  # ACLのUnion-Findを利用
```

### 初期化処理
各マスを独立した集合として初期化：
```python
n = 5  # 例: マス数5
dsu = DSU(n + 1)  # 1-based indexing

# 各集合の情報管理用配列
color_of = [i for i in range(n+1)]  # 初期色はマス番号
range_of = [[i,i] for i in range(n+1)]  # 各集合の範囲
color_count = *(n+1)
for i in range(1, n+1):
    color_count[i] = 1  # 初期状態では各マスが独立
```

### 塗装クエリ処理（タイプ1）
1. 対象マスの連結成分を取得
2. 色変更に伴うカウント更新
3. 隣接する同色領域との統合

```python
def process_paint(x, new_color):
    leader = dsu.leader(x)
    current_color = color_of[leader]
    
    if current_color == new_color:
        return
    
    # カウント更新
    left, right = range_of[leader]
    color_count[current_color] -= (right - left + 1)
    color_count[new_color] += (right - left + 1)
    
    # 左側と統合
    if left > 1:
        left_leader = dsu.leader(left-1)
        if color_of[left_leader] == new_color:
            dsu.merge(leader, left_leader)
            leader = dsu.leader(leader)
            left = range_of[left_leader]
    
    # 右側と統合
    if right  1 and color_of[left_leader] == new_color:
    dsu.merge(leader, left_leader)  # 高速な統合
```


# ACコード1
```python:ac.py
# pip install git+https://github.com/not522/ac-library-python
from atcoder.dsu import DSU  # ACLのUnion-Find（DSU）をインポート

def main():
    # 入力処理（n: 領域数, q: クエリ数）
    n, q = map(int, input().split())
    
    # 定数定義（クエリ種別）
    QUERY_TYPE_PAINT = 1  # 領域塗りつぶしクエリ
    QUERY_TYPE_COUNT = 2  # 色カウント取得クエリ

    # DSU初期化（1-based indexingのためn+1で作成）
    dsu = DSU(n + 1)
    
    # 各集合の管理用データ構造
    color_of = [i for i in range(n + 1)]  # 集合代表の色（初期値は自身の番号）
    range_of = [[i, i] for i in range(n + 1)]  # 各集合がカバーする範囲 [left, right]（閉区間）
    
    # 色ごとの面積カウント（インデックス0は未使用）
    color_count = [0] * (n + 1)
    for i in range(1, n + 1):
        color_count[i] = 1  # 初期状態では各領域が独立
    color_count[0] = 0  # 未使用領域のカウント

    def update_color_count(leader: int, new_color: int):
        """色のカウントを更新するヘルパー関数
        Args:
            leader: 集合の代表元
            new_color: 新しい色
        """
        nonlocal color_count    # 外側の関数の変数を内側の関数で変更したい場合に使う
        left, right = range_of[leader]
        color_count[color_of[leader]] -= (right - left + 1)  # 旧色の面積を減算
        color_count[new_color] += (right - left + 1)         # 新色の面積を加算

    # クエリ処理ループ
    for _ in range(q):
        query = list(map(int, input().split()))
        
        if query[0] == QUERY_TYPE_PAINT:
            # 領域塗りつぶしクエリ
            x, new_color = query[1], query[2]
            leader = dsu.leader(x)          # xが属する集合の代表元を取得
            current_color = color_of[leader]  # 現在の色
            
            if current_color == new_color:
                continue  # 同じ色の場合は処理不要
            
            update_color_count(leader, new_color)  # カウント更新
            
            # 左側の領域と結合可能かチェック
            left, right = range_of[leader]
            if left > 1:
                left_leader = dsu.leader(left - 1)
                if color_of[left_leader] == new_color:  # 左側が同じ色の場合
                    dsu.merge(leader, left_leader)       # 集合を結合
                    leader = dsu.leader(leader)          # 新しい代表元を取得
                    left = range_of[left_leader][0]      # 左端を更新

            # 右側の領域と結合可能かチェック
            if right < n:
                right_leader = dsu.leader(right + 1)
                if color_of[right_leader] == new_color:  # 右側が同じ色の場合
                    dsu.merge(leader, right_leader)       # 集合を結合
                    leader = dsu.leader(leader)           # 新しい代表元を取得
                    right = range_of[right_leader][1]     # 右端を更新

            # 代表元の情報を更新
            color_of[leader] = new_color
            range_of[leader] = [left, right]
            
        elif query[0] == QUERY_TYPE_COUNT:
            # 色の面積取得クエリ
            c = query[1]
            print(color_count[c])  # 該当色の総面積を出力

if __name__ == "__main__":
    main()
```