Super Sequence Scoring System

この解説は $I$ 問題の解説を理解している前提で書かれています。

$I$ 問題と同様に、遅延セグメント木の各ノードに $cnt[a]$ と $pair[a][b]$ を持たせます。区間の結合方法やタイプ $2$ のクエリの処理も同じです。

変更する必要があるのは、遅延作用の表し方です。

今回の各更新は、区間内の値 $a$ を別の値 $f(a)$ に変更する操作とみなせます。そこで、遅延作用として、各 $0\leq a<M$ に対する変換先 $to[a]$ を管理します。

各クエリに対応する変換は次の通りです。

• タイプ $1$：$to[a] = (a+x) \bmod M$
• タイプ $3$：$to[a] = (a*x) \bmod M$
• タイプ $4$：$to[a]=b$, $to[b]=a$ とし、それ以外は $to[c]=c$

この変換をノード $S$ に作用させた後のノードを $S'$ とすると、各 $a,b$ について

• $S'.cnt[to[a]] \mathrel{+}= S.cnt[a]$
• $S'.pair[to[a]][to[b]] \mathrel{+}= S.pair[a][b]$

と更新します。

タイプ $3$ の操作では、異なる値が同じ値に移ることがあります。例えば $M=4,\ x=2$ のとき、$0$ と $2$ はどちらも $0$ に変化します。そのため、更新先への代入ではなく加算を行う必要があります。

次に、遅延作用の合成を考えます。

すでに保留されている変換を $g$、その後に新しく作用させる変換を $f$ とします。元の値 $a$ は、まず $g(a)$ に変化し、その後 $f(g(a))$ に変化します。

したがって、これらを合成した変換を $h$ とすると、各 $a$ について $h(a)=f(g(a))$ です。配列で表すと、$h.to[a]=f.to[g.to[a]]$ と求められます。

以上を適切に実装することで、この問題に答えることができます。

区間の結合と遅延作用の適用には $O(M^2)$、遅延作用の合成には $O(M)$ かかるため、全体の計算量は $O((N+Q\log N)M^2)$、空間計算量は $O(NM^2)$ です。