結果

問題 No.2080 Simple Nim Query
コンテスト
ユーザー lam6er
提出日時 2025-04-15 22:21:01
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 419 ms / 3,000 ms
コード長 2,958 bytes
コンパイル時間 179 ms
コンパイル使用メモリ 82,160 KB
実行使用メモリ 109,012 KB
最終ジャッジ日時 2025-04-15 22:22:37
合計ジャッジ時間 3,759 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 8
権限があれば一括ダウンロードができます

ソースコード

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()))
    A = [0] + A  # 1-based indexing

    # Segment tree to track the rightmost index where A[i] > 1 in a range
    class SegmentTree:
        def __init__(self, data):
            self.n = len(data) - 1  # data is 1-based
            self.size = 1
            while self.size < self.n:
                self.size <<= 1
            self.tree = [-1] * (2 * self.size)
            # Initialize leaves
            for i in range(1, self.n + 1):
                self.tree[self.size + i - 1] = i if data[i] > 1 else -1
            # Build the tree
            for i in range(self.size - 1, 0, -1):
                left = self.tree[2 * i]
                right = self.tree[2 * i + 1]
                self.tree[i] = max(right, left) if right != -1 else left

        def update(self, pos, value):
            pos += self.size - 1  # pos in tree is size + pos - 1
            if value > 1:
                self.tree[pos] = (pos - self.size + 1)
            else:
                self.tree[pos] = -1
            pos >>= 1
            while pos >= 1:
                left = self.tree[2 * pos]
                right = self.tree[2 * pos + 1]
                new_val = max(right, left) if right != -1 else left
                if self.tree[pos] == new_val:
                    break
                self.tree[pos] = new_val
                pos >>= 1

        def query_rightmost(self, l, r):
            res = -1
            l += self.size - 1
            r += self.size - 1
            while l <= r:
                if l % 2 == 1:
                    current = self.tree[l]
                    if current != -1:
                        if res == -1 or current > res:
                            res = current
                    l += 1
                if r % 2 == 0:
                    current = self.tree[r]
                    if current != -1:
                        if res == -1 or current > res:
                            res = current
                    r -= 1
                l >>= 1
                r >>= 1
            return res

    st = SegmentTree(A)

    for _ in range(Q):
        parts = sys.stdin.readline().split()
        T = int(parts[0])
        X = int(parts[1])
        Y = int(parts[2])
        if T == 1:
            # Update A[X] to Y
            A[X] = Y
            st.update(X, Y)
        else:
            # Query [X, Y]
            rightmost = st.query_rightmost(X, Y)
            if rightmost != -1:
                distance = Y - rightmost
                if distance % 2 == 0:
                    print("F")
                else:
                    print("S")
            else:
                length = Y - X + 1
                if length % 2 == 1:
                    print("F")
                else:
                    print("S")

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