結果

問題 No.2292 Interval Union Find
ユーザー LyricalMaestro
提出日時 2025-07-04 21:59:55
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 5,963 bytes
コンパイル時間 364 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 263,168 KB
最終ジャッジ日時 2025-07-04 22:00:24
合計ジャッジ時間 29,026 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 4 TLE * 1 -- * 39
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/2292


class LazySegmentTree:
    """
    非再帰版遅延セグメント木。
    更新は「加法」、取得は「最大値」のもの限定。
    取得のところの都合で取得演算子は可換になっている必要がある。
    """

    def __init__(self, init_array):
        n = 1
        while n < len(init_array):
            n *= 2
        
        self.size = n
        self.array = [0] * (2 * self.size)
        self.weights = [0] * (2 * self.size)
        self.lazy_array = [0 for _ in range(2 * self.size)]
        for i, a in enumerate(init_array):
            self.array[self.size + i] = a
            self.weights[self.size + i] = 1
        
        end_index = self.size
        start_index = end_index // 2
        while start_index >= 1:
            for i in range(start_index, end_index):
                self.array[i] = self.array[2 * i] + self.array[2 * i + 1]
                self.weights[i] = self.weights[2 * i] + self.weights[2 * i + 1]
            end_index = start_index
            start_index = end_index // 2
    
    def _propagates(self, *ids):
        for i in reversed(ids):
            self._propagate(i)

    def _propagate(self, i):
        v = self.lazy_array[i]
        if v == 0:
            return
        
        if i < self.size:
            self._op(2 * i, v)
            self._op(2 * i + 1, v)

        self.lazy_array[i] = 0

    def _op(self, index, v):
        self.lazy_array[index] = v
        if v == 1:
            self.array[index] = 0
        elif v == 2:
            self.array[index] = self.weights[index]


    def _get_target_index(self, l, r):
        L = l + self.size; R = r + self.size
        lm = (L // (L & -L)) >> 1
        rm = (R // (R & -R)) >> 1
        while 0 < L and L < R:
            if R <= rm:
                yield R
            if L <= lm:
                yield L
            L >>= 1; R >>= 1
        while L > 0:
            yield L
            L >>= 1

    def add(self, l, r, x):
        # 2. 区間[l, r)のdata, lazyの値を更新
        L = self.size + l; R = self.size + r
        *ids, = self._get_target_index(l, r)
        self._propagates(*ids)
        while L < R:
            if R & 1:
                R -= 1
                self._op(R, x)
            if L & 1:
                self._op(L, x)
                L += 1
            L >>= 1; R >>= 1

        # 3. 伝搬させた区間について、ボトムアップにdataの値を伝搬する
        for i in ids:
            if i < self.size:
                self.array[i] = self.array[2 * i] + self.array[2 * i +  1]

    def get_sum(self, l, r):
        # 1. トップダウンにlazyの値を伝搬
        self._propagates(*self._get_target_index(l, r))
        L = self.size + l; R = self.size + r

        # 2. 区間[l, r)の最大値を求める
        s = 0
        while L < R:
            if R & 1:
                R -= 1
                s += self.array[R]
            if L & 1:
                s += self.array[L]
                L += 1
            L >>= 1; R >>= 1
        return s



def main():
    N, Q = map(int, input().split())
    queries = []
    for _ in range(Q):
        values = tuple(map(int, input().split()))
        queries.append(values)

    # 座標圧縮
    v_set = set()
    for values in queries:
        if values[0] <= 3:
            _, u, v = values
            u -= 1
            v -= 1
            v_set.add(u)
            v_set.add(u + 1)
            v_set.add(v)
            v_set.add(v + 1)
        else:
            _, v = values
            v -= 1
            v_set.add(v)
            v_set.add(v + 1)
    v_list = list(v_set)
    v_list.sort()
    v_map = {}
    for i, v in enumerate(v_list):
        v_map[v] = i
    v_max = len(v_list)

    array = [1] * v_max
    lazy_seg_tree = LazySegmentTree(array)

    for values in queries:
        if values[0] == 1:
            _, l, r = values
            l -= 1
            r -= 1
            l_ = v_map[l]
            r_ = v_map[r]
            if l_ < r_:
                lazy_seg_tree.add(l_ + 1, r_ + 1, 1)
        elif values[0] == 2:
            _, l, r = values
            l -= 1
            r -= 1
            l_ = v_map[l]
            r_ = v_map[r]
            lazy_seg_tree.add(l_ + 1, r_ + 1, 2)
        elif values[0] == 3:
            _, u, v = values
            u -= 1
            v -= 1
            u_ = v_map[u]
            v_ = v_map[v]

            u_index = lazy_seg_tree.get_sum(0, u_ + 1)
            v_index = lazy_seg_tree.get_sum(0, v_ + 1)
            if u_index == v_index:
                print(1)
            else:
                print(0)
        elif values[0] == 4:
            _, u = values
            u -= 1
            u_ = v_map[u]
            u_low_index = lazy_seg_tree.get_sum(0, u_ + 1)
            low = 0
            high = u_
            while high - low > 1:
                mid = (high + low) // 2
                if lazy_seg_tree.get_sum(0, mid + 1) >= u_low_index:
                    high = mid
                else:
                    low = mid
            if lazy_seg_tree.get_sum(0, low + 1) >= u_low_index:
                v0 = low
            else:
                v0 = high
            
            if u_low_index == lazy_seg_tree.get_sum(0, v_max):
                print(N - v_list[v0])
            else:
                u_high_index = 1 + u_low_index
                low = u_
                high = v_max - 1
                while high - low > 1:
                    mid = (high + low) // 2
                    if lazy_seg_tree.get_sum(0, mid + 1) >= u_high_index:
                        high = mid
                    else:
                        low = mid
                if lazy_seg_tree.get_sum(0, low + 1) >= u_high_index:
                    v1 = low
                else:
                    v1 = high
                print(v_list[v1] - v_list[v0])












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