結果

問題 No.2080 Simple Nim Query
コンテスト
ユーザー flygon
提出日時 2022-09-25 22:51:54
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 889 ms / 3,000 ms
コード長 1,185 bytes
コンパイル時間 378 ms
コンパイル使用メモリ 82,400 KB
実行使用メモリ 121,288 KB
最終ジャッジ日時 2024-06-12 07:25:37
合計ジャッジ時間 6,583 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

n,q = map(int,input().split())
a = list(map(int,input().split()))
qs = [list(map(int,input().split())) for i in range(q)]
seg_len = 1<<19 # > 5*(10**5)
seg = [0]*(2*seg_len)

# 必要に応じて初期状態構築
for i in range(n):
  if a[i] != 1:
    seg[seg_len+i+1] = 1
for i in range(seg_len)[::-1]:
  seg[i] = seg[i*2]+ seg[i*2+1]


def update(pos,x):
  pos += seg_len
  seg[pos] = x 
  while True: 
    pos >>= 1 
    if not pos: break 
    seg[pos] = seg[pos<<1] + seg[pos<<1|1]

def get_query(l,r):
  l += seg_len; r += seg_len
  res = 0 
  while l < r: 
    if l & 1: 
      res += seg[l] 
      l += 1 
    if r & 1: 
      r -= 1 
      res += seg[r] 
    l >>= 1; r >>= 1
  return res

for t,x,y in qs:
  if t == 1:
    if y == 1:
      update(x,0)
    else:
      update(x,1)
  else:
    tmp = get_query(x,y+1)
    ln = y-x+1
    if tmp == 0:
      if ln % 2 == 1:
        print("F")
      else:
        print("S")
    else:
      l = x
      r = y+1
      while r-l > 1:
        m = (r+l)//2
        p = get_query(m,y+1)
        if p >= 1:
          l = m
        else:
          r = m
      if (y - l) % 2 == 0:
        print("F")
      else:
        print("S")
0