No.619 CardShuffle

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 29
作問者 : くれちーくれちー / テスター : 37zigen37zigen
5 ProblemId : 2029 / 出題時の順位表
Advent Calendar Contest Advent Calendar 2017 19日目の問題です。

問題文

12月も折り返し、Y君はクリスマスカードの準備をしているようです。

0 1 2 3 4 5 6 7 8 9 + * のいずれか一つが書かれたカード $N$ 枚の列 $C_1, C_2, \dots, C_N$ が与えられます。すべてのカードは、+ または * の書かれた演算子カードと、それ以外の数字カードの2種類に分類されます。$C_1, C_N$ は数字カードで、数字カードと演算子カードは1枚ずつ交互に並んでいます。

数字カードを1桁の整数、演算子カード + を加算、* を乗算と見なしたとき、カード列 $C_X, C_{X+1}, \dots, C_Y$ がつくる式の値を $f(X, Y)$ とします。例えば、$C_1 =$ 5、$C_2 =$ +、$C_3 =$ 7、$C_4 =$ *、$C_5 =$ 4、$C_6 =$ +、$C_7 =$ 1 のとき、$f(1, 5) = 5 + 7 \times 4 = 5 + 28 = 33$、$f(5, 7) = 4 + 1 = 5$ となります。

以下の2種類のクエリが $Q$ 個与えられるので、これを順番に処理してください。

  • 交換クエリ:同じ種類のカード $C_X$ と $C_Y$ を交換する。
  • 質問クエリ:$f(X, Y) \bmod (10 ^ 9 + 7)$ を出力する。

入力

$N$
$C_1$ $C_2$ $\dots$ $C_N$
$Q$
$T_1$ $X_1$ $Y_1$
$T_2$ $X_2$ $Y_2$
$\vdots$
$T_Q$ $X_Q$ $Y_Q$

数値はすべて整数です。以下の制約を満たします。

  • $3 \le N \le 10^5-1$
  • $N$ は奇数
  • $i$ が奇数ならば $C_i \in \{$ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 $\}$
  • $i$ が偶数ならば $C_i \in \{$ +, * $\}$
  • $1 \le Q \le 10^5$
  • $i \ne Q$ ならば $T_i \in \{$ !, ? $\}$
  • $T_Q =$ ?
  • $1 \le X_i \lt Y_i \le N$
  • $T_i =$ ! のとき、これは交換クエリを表し、
    • カード $C_{X_i}$ と $C_{Y_i}$ の種類は同じ (すなわち $X_i \equiv Y_i \pmod{2}$)
  • $T_i =$ ? のとき、これは質問クエリを表し、
    • $X_i, Y_i$ は奇数

出力

すべての質問クエリに対して1行ずつ出力し、最後に改行してください。

サンプル

サンプル1
入力
7
5 + 7 * 4 + 1
6
? 1 5
? 5 7
! 2 4
? 1 5
! 3 7
? 1 7
出力
33
5
39
16

問題文の例です。

  1. 5 + 7 * 4 + 1
  2. $f(1, 5) = 5 + 7 \times 4 = 33$
  3. $f(5, 7) = 4 + 1 = 5$
  4. 5 * 7 + 4 + 1
  5. $f(1, 5) = 5 \times 7 + 4 = 39$
  6. 5 * 1 + 4 + 7
  7. $f(1, 7) = 5 \times 1 + 4 + 7 = 16$

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。