No.2395 区間二次変換一点取得
タグ : / 解いたユーザー数 80
作問者 : 👑
p-adic
/ テスター :
ecottea
hiro1729
問題文
入力に $3$ 個の正整数 $N, B, Q$ と、$Q$ 個のクエリ（後述）が与えられます。
長さ $N$ の非負整数列 $a$ と $N$ 以下の正整数 $i$ に対し、$a_i$ で $a$ の $i$ 個目の成分を表します。
最初に長さ $N$ の非負整数列 $X, Y, Z$ が、いずれも $1$ のみを成分に持つ数列として与えられています。
各クエリは、$1 \leq L \leq M \leq R \leq N$ を満たす整数 $L, M, R$ の組 $(L,M,R)$ です。
クエリ $(L,M,R)$ は以下のように処理します：
- まず $L \leq i \leq R$ を満たす各正整数 $i$ に対し、$X$ の $i$ 個目の成分を $X_i + 1$ で置き換えることで $X$ を更新する。
- 次に $L \leq i \leq R$ を満たす各正整数 $i$ に対し、$Y$ の $i$ 個目の成分を $3Y_i + 2X_i Z_i$ で置き換えることで $Y$ を更新する。
- 更に $L \leq i \leq R$ を満たす各正整数 $i$ に対し、$Z$ の $i$ 個目の成分を $3Z_i$ で置き換えることで $Z$ を更新する。
- 最後に $X_M, Y_M, Z_M$ をそれぞれ $B$ で割った余りを求める。（以下、これらの値をこのクエリに対する回答と呼ぶ）
手順2において、$X_i$ は手順1で更新された後の $X$ を参照していることに注意してください。また手順4において、$X_M, Y_M, Z_M$ は手順1,2,3で更新された後の $X, Y, Z$ を参照していることに注意してください。
$Q$ 個のクエリを与えられた順に処理してください。
入力
入力は次の形式で標準入力から $1 + Q$ 行で与えられます：
- $1$ 行目に $N, B, Q$ が半角空白区切りで与えられます。
- $Q$ 以下の各正整数 $q$ に対し、$1 + q$ 行目に $q$ 個目のクエリを $(L_q,M_q,R_q)$ と置くと、$L_q, M_q, R_q$ が半角空白区切りで与えられます。
$N$ $B$ $Q$ $L_1$ $M_1$ $R_1$ $\vdots$ $L_Q$ $M_Q$ $R_Q$
制約
入力は以下の制約を満たします：
- $N$ は $1 \leq N \leq 10^5$ を満たす整数である。
- $B$ は $1 \leq B \leq 10^9$ を満たす整数である。
- $Q$ は $1 \leq Q \leq 10^5$ を満たす整数である。
- $Q$ 以下の任意の正整数 $q$ に対し、$L_q, M_q, R_q$ は $1 \leq L_q \leq M_q \leq R_q \leq N$ を満たす整数である。
出力
$Q$ 以下の各正整数 $q$ に対し、$q$ 行目に $q$ 個目のクエリに対する回答を半角空白区切りで出力してください。
最後に改行してください。
サンプル
サンプル1
入力
1 1 1 1 1 1
出力
0 0 0
最初は $X, Y, Z$ がいずれも $(1)$ として与えられています。
クエリ $(L_1,M_1,R_1) = (1,1,1)$ により、まず $X$ が
$\displaystyle (X_1 + 1) = (1+1) = (2) $
に置き換わり、次に $Y$ が
$\displaystyle (3Y_1 + 2X_1 Z_1) = (3 \times 1 + 2 \times 2 \times 1) = (7) $
に置き換わり、更に $Z$ が
$\displaystyle (3Z_1) = (3 \times 1) = (3) $
に置き換わります。更新後の $(X,Y,Z)$ について $(X_M,Y_M,Z_M) = (X_1,Y_1,Z_1) = (2,7,3)$ であり、$2,7,3$ をそれぞれ $B = 1$ で割った余りは $0,0,0$ です。
今回は $Q = 1$ であるため、これで全ての処理が終了します。
サンプル2
入力
2 2 1 1 1 1
出力
0 1 1
最初は $X, Y, Z$ がいずれも $(1,1)$ として与えられています。
クエリ $(L_1,M_1,R_1) = (1,1,1)$ により、まず $X$ が
$\displaystyle (X_1 + 1, X_2) = (1+1,1) = (2,1) $
に置き換わり、次に $Y$ が
$\displaystyle (3Y_1 + 2X_1 Z_1, Y_2) = (3 \times 1 + 2 \times 2 \times 1, 1) = (7,1) $
に置き換わり、更に $Z$ が
$\displaystyle (3Z_1, Z_2) = (3 \times 1, 1) = (3,1) $
に置き換わります。更新後の $(X,Y,Z)$ について $(X_M,Y_M,Z_M) = (X_1,Y_1,Z_1) = (2,7,3)$ であり、$2,7,3$ をそれぞれ $B = 2$ で割った余りは $0,1,1$ です。
今回は $Q = 1$ であるため、これで全ての処理が終了します。
サンプル3
入力
2 4 2 1 1 2 2 2 2
出力
2 3 3 3 3 1
最初は $X, Y, Z$ がいずれも $(1,1)$ として与えられています。
クエリ $(L_1,M_1,R_1) = (1,1,2)$ により、まず $X$ が
$\displaystyle (X_1 + 1, X_2 + 1) = (1+1,1+1) = (2,2) $
に置き換わり、次に $Y$ が
$\displaystyle (3Y_1 + 2X_1 Z_1, 3Y_2 + 2X_2 Z_2) = (3 \times 1 + 2 \times 2 \times 1, 3 \times 1 + 2 \times 2 \times 1) = (7,7) $
に置き換わり、更に $Z$ が
$\displaystyle (3Z_1, 3Z_2) = (3 \times 1, 3 \times 1) = (3,3) $
に置き換わります。更新後の $(X,Y,Z)$ について $(X_M,Y_M,Z_M) = (X_1,Y_1,Z_1) = (2,7,3)$ であり、$2,7,3$ をそれぞれ $B = 4$ で割った余りは $2,3,3$ です。
$2$ 個目のクエリ $(L_2,M_2,R_2) = (2,2,2)$ により、まず $X$ が
$\displaystyle (X_1,X_2 + 1) = (2,2+1) = (2,3) $
に置き換わり、次に $Y$ が
$\displaystyle (Y_1,3Y_2 + 2X_2 Z_2) = (7,3 \times 7 + 2 \times 3 \times 3) = (7,39) $
に置き換わり、更に $Z$ が
$\displaystyle (Z_1,3Z_2) = (3,3 \times 3) = (3,9) $
に置き換わります。更新後の $(X,Y,Z)$ について $(X_M,Y_M,Z_M) = (X_2,Y_2,Z_2) = (3,39,9)$ であり、$3,39,9$ をそれぞれ $B = 4$ で割った余りは $3,3,1$ です。
今回は $Q = 2$ であるため、これで全ての処理が終了します。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。