結果

問題 No.876 Range Compress Query
ユーザー toyuzukotoyuzuko
提出日時 2020-03-09 18:52:05
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
TLE  
実行時間 -
コード長 3,728 bytes
コンパイル時間 599 ms
コンパイル使用メモリ 13,312 KB
実行使用メモリ 29,244 KB
最終ジャッジ日時 2024-11-08 18:28:45
合計ジャッジ時間 18,783 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 30 ms
11,264 KB
testcase_01 AC 37 ms
11,264 KB
testcase_02 AC 31 ms
11,264 KB
testcase_03 AC 38 ms
11,264 KB
testcase_04 AC 31 ms
11,264 KB
testcase_05 AC 31 ms
11,264 KB
testcase_06 AC 36 ms
11,136 KB
testcase_07 AC 37 ms
11,264 KB
testcase_08 AC 36 ms
11,136 KB
testcase_09 AC 36 ms
11,264 KB
testcase_10 AC 36 ms
11,264 KB
testcase_11 TLE -
testcase_12 AC 1,807 ms
26,572 KB
testcase_13 AC 1,767 ms
26,964 KB
testcase_14 TLE -
testcase_15 AC 1,415 ms
26,608 KB
testcase_16 TLE -
testcase_17 TLE -
testcase_18 TLE -
権限があれば一括ダウンロードができます

ソースコード

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