問題一覧 > 通常問題

No.2080 Simple Nim Query

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 67
作問者 : taiga0629kyoprotaiga0629kyopro / テスター : AngrySadEightAngrySadEight 👑 ygussanyygussany
2 ProblemId : 8437 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-09-18 18:01:04

問題文

taiga 君は次のような問題を作りました。

Simple Nim

整数列 $(C_1,C_2,\dots ,C_k)$ を用いて F 君と S 君は石取りゲームを行います。 最初 $k$ 個の石の山が左右一列に並んでおり、左から $i$ 番目の石の山には $C_i$ 個の石があります。 F 君から始めて $2$ 人は交互に以下の操作を繰り返します。

  • 石が $1$ 個以上残っている山のうち最も右にあるものを選ぶ。 その山に $n$ 個の石があるとき、$1$ 個以上 $n$ 個以下の任意の個数の石をその山から取り除く。

先に操作できなくなったプレイヤーが負けとなります。どちらが勝ちますか?

長さ $N$ の整数列 $A$ と $Q$ 個のクエリが与えられます。 $i$ 番目のクエリでは三つの整数 $T_i,X_i,Y_i$ が与えられるので以下の処理を行ってください。

  • $T_i=1$ のとき、$A_{X_i}$ を $Y_i$ で置き換える。

  • $T_i=2$ のとき、$C=(A_{X_i},A_{X_i+1},\dots,A_{Y_i})$ とした時の問題 "Simple Nim" の答えを出力する。

入力

$N$ $Q$
$A_1$ $A_2$ $\dots$ $A_N$
$T_1$ $X_1$ $Y_1$
$T_2$ $X_2$ $Y_2$
$\vdots$
$T_Q$ $X_Q$ $Y_Q$

  • $1 \le N \le 2×10^5$
  • $1 \le Q \le 2×10^5$
  • $1 \le A_i \le 10^9$
  • $T_i$ は $1$ または $2$
  • $T_i=1$ なら $1 \le X_i \le N$ かつ $1 \le Y_i \le 10^9$
  • $T_i=2$ なら $1 \le X_i \le Y_i \le N$
  • 入力は全て整数
  • 出力

    $T_i=2$ であるような各クエリについて、"Simple Nim" で F 君が勝つなら F と、 S 君が勝つなら S と出力してください。

    サンプル

    サンプル1
    入力
    2 1
    2 1
    2 1 2
    出力
    S

    $C=(2,1)$ です。最初 F 君は左から $2$ 番目の山から石を $1$ 個取る以外の選択肢はありません。 すると S 君は左から $1$ 番目の山から石を $2$ 個取ることでゲームに勝つことができます。

    サンプル2
    入力
    2 1
    1 2
    2 1 2
    出力
    F

    $C=(1,2)$ です。最初 F 君が左から $2$ 番目の山から石を $1$ 個とります。そうすると、次に S 君は左から $2$ 番目の山から石を $1$ 個取る以外の選択肢はありません。よって次のターンに F 君が左から $1$ 番目の山から石を $1$ 個とることで F 君は勝利します。

    サンプル3
    入力
    3 3
    3 1 4
    2 1 2
    1 2 2
    2 1 3
    出力
    S
    F

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。