結果

問題 No.876 Range Compress Query
ユーザー toyuzukotoyuzuko
提出日時 2020-03-09 18:52:30
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 581 ms / 2,000 ms
コード長 3,728 bytes
コンパイル時間 217 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 99,456 KB
最終ジャッジ日時 2024-11-08 18:31:26
合計ジャッジ時間 6,457 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 49 ms
53,376 KB
testcase_01 AC 73 ms
67,840 KB
testcase_02 AC 47 ms
53,632 KB
testcase_03 AC 77 ms
68,608 KB
testcase_04 AC 55 ms
60,928 KB
testcase_05 AC 53 ms
60,416 KB
testcase_06 AC 75 ms
68,736 KB
testcase_07 AC 76 ms
67,968 KB
testcase_08 AC 73 ms
67,072 KB
testcase_09 AC 71 ms
66,688 KB
testcase_10 AC 71 ms
66,688 KB
testcase_11 AC 558 ms
97,416 KB
testcase_12 AC 505 ms
95,460 KB
testcase_13 AC 518 ms
96,384 KB
testcase_14 AC 568 ms
97,524 KB
testcase_15 AC 478 ms
98,176 KB
testcase_16 AC 559 ms
99,456 KB
testcase_17 AC 557 ms
99,456 KB
testcase_18 AC 581 ms
99,328 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

class SegmentTree():
    def __init__(self, arr, func=min, ie=2**63):
        self.n = 2**(len(arr) - 1).bit_length()
        self.ie = ie
        self.func = func
        self.tree = [ie for _ in range(2 * self.n)]
        for i in range(len(arr)):
            self.tree[self.n + i - 1] = arr[i]
        for i in range(self.n - 1)[::-1]:
            self.tree[i] = func(self.tree[2 * i + 1], self.tree[2 * i + 2])

    def set(self, index, x):
        index += self.n - 1
        self.tree[index] = x
        while index:
            index = (index - 1) // 2
            self.tree[index] = self.func(self.tree[2 * index + 1],
                                         self.tree[2 * index + 2])

    def query(self, left, right):
        if right <= left:
            return self.ie
        left += self.n - 1
        right += self.n - 2
        tmp_l = self.ie
        tmp_r = self.ie
        while right - left > 1:
            if left & 1 == 0:
                tmp_l = self.func(tmp_l, self.tree[left])
            if right & 1 == 1:
                tmp_r = self.func(self.tree[right], tmp_r)
                right -= 1
            left = left // 2
            right = (right - 1) // 2
        if left == right:
            tmp_l = self.func(tmp_l, self.tree[left])
        else:
            tmp_l = self.func(
                self.func(tmp_l, self.tree[left]), self.tree[right])
        return self.func(tmp_l, tmp_r)


class SegmentTreeDual():
    def __init__(self, arr, op=lambda x, y: y if y != -1 else x, ie=-1):
        self.h = (len(arr) - 1).bit_length()
        self.n = 2**self.h
        self.ie = ie
        self.op = op
        self.val = [ie for _ in range(self.n)]
        self.laz = [ie for _ in range(2 * self.n)]
        for i in range(len(arr)):
            self.val[i] = arr[i]

    def propagate(self, k):
        if self.laz[k] == self.ie: return
        if self.n <= k:
            self.val[k - self.n] = self.op(self.val[k - self.n], self.laz[k])
            self.laz[k] = self.ie
        else:
            self.laz[2 * k] = self.op(self.laz[2 * k], self.laz[k])
            self.laz[2 * k + 1] = self.op(self.laz[2 * k + 1], self.laz[k])
            self.laz[k] = self.ie

    def update(self, left, right, x):
        left += self.n
        right += self.n
        '''
        for i in range(self.h)[::-1]:
            self.propagate(left >> i)
            self.propagate(right >> i)
        '''
        while right - left > 0:
            if right & 1:
                right -= 1
                self.laz[right] = self.op(self.laz[right], x)
            if left & 1:
                self.laz[left] = self.op(self.laz[left], x)
                left += 1
            left >>= 1
            right >>= 1

    def get(self, index):
        res = self.val[index]
        index += self.n
        while index > 0:
            res = self.op(res, self.laz[index])
            index //= 2
        return res


import sys
input = sys.stdin.readline
from operator import add

N, Q = map(int, input().split())
A = list(map(int, input().split()))
B = [A[i] != A[i + 1] for i in range(N - 1)]

std = SegmentTreeDual(A, add, 0)
st = SegmentTree(B, add, 0)
ans = []

for _ in range(Q):
    q = list(map(int, input().split()))
    if q[0] == 1:
        l, r, x = q[1:]
        std.update(l - 1, r, x)
        if l > 1:
            if std.get(l - 1) == std.get(l - 2):
                st.set(l - 2, 0)
            else:
                st.set(l - 2, 1)
        if r < N:
            if std.get(r) == std.get(r - 1):
                st.set(r - 1, 0)
            else:
                st.set(r - 1, 1)
    if q[0] == 2:
        l, r = q[1:]
        ans.append(st.query(l - 1, r - 1) + 1)

print('\n'.join(map(str, ans)))
0