「区間をペアで管理するやつ」をPythonでライブラリ化しました

　区間をペアで管理するデータ構造は、mex（minimum excluded value、含まれない中で最小の値）を高速で求める時などに使われます。C++ での実装は[この記事](https://rsk0315.hatenablog.com/entry/2020/10/11/125049)にまとまっていますが、Python での実装が見当たらなかったため、実装してライブラリにしました。

（2025/04/25 追記）
C++ ですが、より用途が広いライブラリをけんちょんさんが作ってくれました。
https://github.com/drken1215/algorithm/blob/master/DataStructure/intervals_management.cpp

# とりあえずコード

```Python
from sortedcontainers import SortedSet

class Pairset():
    data = None
    
    def __init__(self) -> None:
        self.data = SortedSet()
        self.data.add((-10**18,-10**18))
        self.data.add((10**18,10**18))
    
    def contains(self,x):
        idx = self.data.bisect_right((x,10**18))-1
        L_start,L_end = self.data[idx]
        return x < L_end
    
    def add(self,x):
        idx = self.data.bisect_right((x,10**18))-1
        L_start,L_end = self.data[idx]
        R_start,R_end = self.data[idx+1]
        if x < L_end:
            return False
        if L_end < x and x+1 < R_start:
            self.data.add((x,x+1))
        elif L_end == x and x+1 < R_start:
            self.data.pop(idx)
            self.data.add((L_start,x+1))
        elif L_end < x and x+1 == R_start:
            self.data.pop(idx+1)
            self.data.add((x,R_end))
        else:
            self.data.pop(idx+1)
            self.data.pop(idx)
            self.data.add((L_start,R_end))
        return True
    
    def mex(self,x):
        idx = self.data.bisect_right((x,10**18))-1
        L_start,L_end = self.data[idx]
        if L_end <= x:
            return x
        else:
            return L_end
        
    def expand(self,x):
        idx = self.data.bisect_right((x,10**18))-1
        L_start,L_end = self.data[idx]
        if L_end <= x:
            return x,x            
        else:
            return L_start, L_end
    
    def remove(self,x):
        idx = self.data.bisect_right((x,10**18))-1
        L_start,L_end = self.data[idx]
        if L_end <= x:
            return False
        self.data.pop(idx)
        if L_start < x:
            self.data.add((L_start,x))
        if x+1 < L_end:
            self.data.add((x+1,L_end))
        return True
```

:::note info
`sortedcontainers` を使用していますが、 [tatyam set](https://github.com/tatyam-prime/SortedSet) に慣れている人はそれで済ませるのもありかもしれません
:::

# 使用法

```python
ps = Pairset()
print(ps.mex(0)) # 0
ps.add(0)
print(ps.mex(0)) # 1
ps.add(2)
print(ps.mex(0)) # 1
ps.add(1)
print(ps.mex(0)) # 3
print(ps.expand(1)) # (0,3)
print(ps.contains(1)) # True
ps.remove(1)
print(ps.contains(1)) # False
print(ps.mex(0)) # 1
```

# 解説

　以下、計算量について $N$ を使用済の数が連続している区間の数とします。

## contains(x)

　$x$ が、使用済かどうかを判定します。あれば True、なければ False を返します。
　計算量は $O(\text{log}N)$ です。

## add(x)

　$x$ を使用済にします。すでに使用している場合は何もしませんが、返り値として False を返します。
　計算量は $O(\text{log}N)$ です。

## mex(x)

　$x$ 以上かつ未使用な最小の数を返します。
　計算量は $O(\text{log}N)$ です。

## expand(x)

　$x$ が含まれる連続した使用済の区間（半開区間）を返します。
　自分が含まれる区間いっぱいに膨張するイメージです。
　$x$ が未使用ならば、`(x,x)` を返します。
　返り値を $L,R$ とすると、$R-L$ がその区間の長さ（連続する使用済みの数の個数）になります。
　計算量は $O(\text{log}N)$ です。

## remove(x)

　$x$ を未使用にします。
　元から未使用の場合は何もしませんが、返り値として False を返します。
　計算量は $O(\text{log}N)$ です。

# 使用上の注意

## 半開区間

　参考にした記事は閉区間で管理していましたが、区間長を扱う場合のメリットを考えて、このライブラリでは半開区間を採用しています。

　使用法の例では、内部のデータ構造はこうなっています。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/288125/d17e94e1-656b-45c1-32e0-799d418af420.png)

　つまり、$0,1,2$ が連続していると、その区間は $[0,3)$ になります。

## TLE

　Python の遅さのせいか、私の実装の悪さのせいなのかはわかりませんが、かなり遅いです。通しはしましたが、数個の TLE が取れずに、定数倍の改善を行った末にやっと間に合ったということがありました。

# 実際の提出例

- [ABC271-C](https://atcoder.jp/contests/abc271/submissions/57606291)
- [ABC370-D](https://atcoder.jp/contests/abc370/submissions/57606314)

# 今後の展望

- 区間追加
- 区間削除

　を追加したいです。

　ChatGPT に書かせてできたもの。vereify が済み次第反映させます。

```python
    def add_interval(self, xL, xR):
        idx = self.data.bisect_left((xL, xR))
        if idx > 0:
            prev_start, prev_end = self.data[idx - 1]
            if xL <= prev_end:
                xL = prev_start
                xR = max(xR, prev_end)
                self.data.pop(idx - 1)
                idx -= 1
        while idx < len(self.data):
            next_start, next_end = self.data[idx]
            if next_start > xR:
                break
            xR = max(xR, next_end)
            self.data.pop(idx)

        self.data.add((xL, xR))

    def remove_interval(self, xL, xR):
        idx = self.data.bisect_left((xL, xL))
        if idx > 0:
            L_start, L_end = self.data[idx - 1]
            if L_start <= xL < L_end:
                self.data.pop(idx - 1)
                if L_start < xL:
                    self.data.add((L_start, xL))
                if xR < L_end:
                    self.data.add((xR, L_end))

        while idx < len(self.data):
            L_start, L_end = self.data[idx]
            if L_start >= xR:
                break
            self.data.pop(idx)
            if xR < L_end:
                self.data.add((xR, L_end))
```