結果

問題 No.2080 Simple Nim Query
ユーザー sasa8uyauya
提出日時 2025-07-05 01:41:45
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,214 ms / 3,000 ms
コード長 1,203 bytes
コンパイル時間 382 ms
コンパイル使用メモリ 82,212 KB
実行使用メモリ 107,244 KB
最終ジャッジ日時 2025-07-05 01:41:57
合計ジャッジ時間 9,691 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

class SegmentTree:
  def __init__(self,n,initial_value=0):
    self.n=n
    self.tree=[initial_value]*(2*n)

  def build(self,arr):
    for i in range(self.n):
      self.tree[self.n+i]=arr[i]
    for i in range(self.n-1,0,-1):
      self.tree[i]=max(self.tree[2*i],self.tree[2*i+1])

  def update(self,index,value):
    index+=self.n
    self.tree[index]=value
    while index>1:
      self.tree[index//2]=max(self.tree[index],self.tree[index^1])
      index//=2

  def query(self,left,right):
    left+=self.n
    right+=self.n
    max_val=float('-inf')

    while left<right:
      if left%2==1:
        max_val=max(max_val,self.tree[left])
        left+=1
      if right%2==1:
        right-=1
        max_val=max(max_val,self.tree[right])
      left//=2
      right//=2
    return max_val


n,Q=map(int,input().split())
a=list(map(int,input().split()))
st=SegmentTree(n)
st.build(a)
for _ in range(Q):
  t,x,y=map(int,input().split())
  if t==1:
    st.update(x-1,y)
  if t==2:
    x-=1
    y-=1
    ok=0
    ng=y-x+1+1
    while ng-ok>1:
      m=(ok+ng)//2
      l=y-m+1
      r=y
      if st.query(l,r+1)==1:
        ok=m
      else:
        ng=m
    print("FS"[ok%2] if ok<y-x+1 else "SF"[ok%2])
0