解法：しゃくとり法 考え方 回答例 解法：累積和（+set） 考え方 解法：しゃくとり法考え方3回のしゃくとり法で，$x = P, Q, R$に対し 区間和が$\sum_{[l, r)} A_{l} = x$を満たす$l$の集合$S_{x}$ $l$を$r$に対応させる辞書$f_{x} (l)=r$ を求めておく．Yes…

考え方 回答例 考え方区間$[l, r]$を考える（$1 \leq l \leq r \leq M$）．$l$を固定し，$r$を良い数列になるまで動かす．このとき，$r^{\prime} \geq r$に対し，区間$[l, r^{\prime}]$に対応する数列はすべて良い数列なので，個数をカウントする．上を$l=1,…

方法1 考え方 回答例 方法1考え方 各じゃがいもの種類$i$に対して，$i$スタートで重さの総和が$X$以上になるときの「個数」と「その次の箱に入るじゃがいもの種類$j$」を求めることができる． 上の結果から$i\to j$に辺を張った有向グラフを考えると，周期$N…

考え方 回答例 考え方区間$[1, N]$を，区間$[i, j]$で $X \leq A_{k} \leq Y \:(\forall k \in [i, j])$ を満たすものに分割して考える．あとはこの区間ごとに個数を数えれば良い．区間の左端を$L = i$に固定して，$X, Y$の両方が出てくるまで右端を一つずつ…

考え方 回答例 考え方式変形（因数分解など）で何かを見出そうとしても上手く行かない．2変数の問題は， 2次元平面で考える 1変数を固定して考える とよい．$0 \leq N \leq 10^{18}$だから，$0 \leq a,b \leq 10^{6}$である．よって，$a,b$の全探索はできな…

考え方 回答例. 1 回答例. 2 - dequeを使う 考え方左端と右端を右方向に動かしていけば，$S$の長さの2倍の計算量で全て見ていける．したがって，しゃくとり法で実装すれば良い．あとは，いかにバグらせないかがポイントになる．回答例. 1$X$に変えられる区間…