結果

問題 No.2080 Simple Nim Query
コンテスト
ユーザー lam6er
提出日時 2025-03-20 19:00:40
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 5,676 bytes
コンパイル時間 327 ms
コンパイル使用メモリ 82,640 KB
実行使用メモリ 177,748 KB
最終ジャッジ日時 2025-03-20 19:01:53
合計ジャッジ時間 6,891 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 3 WA * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    sys.setrecursionlimit(1 << 25)
    N, Q = map(int, sys.stdin.readline().split())
    A = list(map(int, sys.stdin.readline().split()))
    
    # Segment tree for rightmost non-zero element
    class RightmostNonZeroNode:
        def __init__(self):
            self.pos = -1
            self.value = 0
        
        def merge(self, left, right):
            if right.pos != -1:
                self.pos = right.pos
                self.value = right.value
            else:
                self.pos = left.pos
                self.value = left.value if left.pos != -1 else 0

    class RightmostNonZeroSegmentTree:
        def __init__(self, data):
            self.n = len(data)
            self.size = 1
            while self.size < self.n:
                self.size <<= 1
            self.tree = [RightmostNonZeroNode() for _ in range(2 * self.size)]
            for i in range(self.n):
                node = self.tree[self.size + i]
                if data[i] != 0:
                    node.pos = i
                    node.value = data[i]
                else:
                    node.pos = -1
                    node.value = 0
            for i in range(self.size - 1, 0, -1):
                self.tree[i].merge(self.tree[2*i], self.tree[2*i+1])
        
        def update(self, pos, value):
            pos += self.size
            node = self.tree[pos]
            if value != 0:
                node.pos = pos - self.size
                node.value = value
            else:
                node.pos = -1
                node.value = 0
            pos >>= 1
            while pos >= 1:
                self.tree[pos].merge(self.tree[2*pos], self.tree[2*pos+1])
                pos >>= 1
        
        def query_rightmost(self, l, r):
            l += self.size
            r += self.size
            res = RightmostNonZeroNode()
            while l <= r:
                if l % 2 == 1:
                    current = self.tree[l]
                    if current.pos != -1 and (res.pos == -1 or current.pos > res.pos):
                        res.pos = current.pos
                        res.value = current.value
                    l += 1
                if r % 2 == 0:
                    current = self.tree[r]
                    if current.pos != -1 and (res.pos == -1 or current.pos > res.pos):
                        res.pos = current.pos
                        res.value = current.value
                    r -= 1
                l >>= 1
                r >>= 1
            return res
    
    # Segment tree for checking if any non-zero in range
    class NonZeroCheckNode:
        def __init__(self):
            self.has_non_zero = False
        
        def merge(self, left, right):
            self.has_non_zero = left.has_non_zero or right.has_non_zero

    class NonZeroCheckSegmentTree:
        def __init__(self, data):
            self.n = len(data)
            self.size = 1
            while self.size < self.n:
                self.size <<= 1
            self.tree = [NonZeroCheckNode() for _ in range(2 * self.size)]
            for i in range(self.n):
                self.tree[self.size + i].has_non_zero = (data[i] != 0)
            for i in range(self.size - 1, 0, -1):
                self.tree[i].merge(self.tree[2*i], self.tree[2*i+1])
        
        def update(self, pos, value):
            pos += self.size
            self.tree[pos].has_non_zero = (value != 0)
            pos >>= 1
            while pos >= 1:
                prev = self.tree[pos].has_non_zero
                self.tree[pos].merge(self.tree[2*pos], self.tree[2*pos+1])
                if prev == self.tree[pos].has_non_zero:
                    break
                pos >>= 1
        
        def query_has_non_zero(self, l, r):
            l += self.size
            r += self.size
            res = False
            while l <= r:
                if l % 2 == 1:
                    res = res or self.tree[l].has_non_zero
                    l += 1
                if r % 2 == 0:
                    res = res or self.tree[r].has_non_zero
                    r -= 1
                l >>= 1
                r >>= 1
            return res
    
    data = A
    # Build the two segment trees
    rnz_tree = RightmostNonZeroSegmentTree(data)
    check_tree = NonZeroCheckSegmentTree(data)
    
    for _ in range(Q):
        parts = sys.stdin.readline().split()
        if not parts:
            continue
        T = int(parts[0])
        X = int(parts[1]) - 1  # convert to 0-based
        Y = int(parts[2])
        if T == 1:
            # Update
            A[X] = Y
            rnz_tree.update(X, Y)
            check_tree.update(X, Y)
        else:
            # Query
            L = X
            R = Y - 1  # parts[2] was Y, the upper bound is 1-based, convert to 0-based
            # Find the rightmost non-zero in [L, R]
            res_node = rnz_tree.query_rightmost(L, R)
            if res_node.pos == -1:
                # All zeros
                print('S')
                continue
            value = res_node.value
            if value > 1:
                print('F')
            else:
                # Check if all to the left are zero
                left_L = L
                left_R = res_node.pos - 1
                if left_L > left_R:
                    # No elements to the left, output F
                    print('F')
                else:
                    has_non_zero = check_tree.query_has_non_zero(left_L, left_R)
                    if has_non_zero:
                        print('S')
                    else:
                        print('F')

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