結果

問題 No.2080 Simple Nim Query
ユーザー lam6er
提出日時 2025-03-31 17:52:19
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,637 bytes
コンパイル時間 227 ms
コンパイル使用メモリ 82,848 KB
実行使用メモリ 169,168 KB
最終ジャッジ日時 2025-03-31 17:53:11
合計ジャッジ時間 13,524 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 1 WA * 5 TLE * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from sys import stdin

class SegmentTreeNode:
    def __init__(self, l, r):
        self.l = l
        self.r = r
        self.left_child = None
        self.right_child = None
        self.has_odd = False
        self.rightmost_odd_pos = -1

def build(l, r, A):
    node = SegmentTreeNode(l, r)
    if l == r:
        val = A[l-1]  # A is 0-based, positions are 1-based in the segment tree
        is_odd = (val % 2) == 1
        node.has_odd = is_odd
        node.rightmost_odd_pos = l if is_odd else -1
        return node
    mid = (l + r) // 2
    node.left_child = build(l, mid, A)
    node.right_child = build(mid+1, r, A)
    node.has_odd = node.left_child.has_odd or node.right_child.has_odd
    node.rightmost_odd_pos = node.right_child.rightmost_odd_pos if node.right_child.rightmost_odd_pos != -1 else node.left_child.rightmost_odd_pos
    return node

def update(node, pos, new_val):
    if node.l == node.r == pos:
        is_odd = (new_val % 2) == 1
        node.has_odd = is_odd
        node.rightmost_odd_pos = pos if is_odd else -1
        return
    if pos <= node.left_child.r:
        update(node.left_child, pos, new_val)
    else:
        update(node.right_child, pos, new_val)
    # Update the current node's info based on children
    node.has_odd = node.left_child.has_odd or node.right_child.has_odd
    node.rightmost_odd_pos = node.right_child.rightmost_odd_pos if node.right_child.rightmost_odd_pos != -1 else node.left_child.rightmost_odd_pos

def query(node, target_l, target_r):
    if node.r < target_l or node.l > target_r:
        return -1
    if target_l <= node.l and node.r <= target_r:
        return node.rightmost_odd_pos if node.has_odd else -1
    right_res = query(node.right_child, target_l, target_r)
    if right_res != -1:
        return right_res
    return query(node.left_child, target_l, target_r)

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr +=1
    Q = int(input[ptr])
    ptr +=1
    A = list(map(int, input[ptr:ptr+N]))
    ptr +=N
    
    # Build segment tree
    root = build(1, N, A)
    
    for _ in range(Q):
        T = int(input[ptr])
        X = int(input[ptr+1])
        Y = int(input[ptr+2])
        ptr +=3
        if T == 1:
            # Update A[X] to Y (X is 1-based)
            update(root, X, Y)
        else:
            # Query [X, Y]
            pos = query(root, X, Y)
            if pos == -1:
                print('S')
            else:
                if pos % 2 == 1:
                    print('F')
                else:
                    print('S')

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