Sequence Scoring System

この問題は遅延セグメント木を用いることで解くことができます。

遅延セグメント木の各ノードに次の情報を持たせます。

• $cnt[a]$：区間内に値 $a$ が何個あるか
• $pair[a][b]$：区間内で $i<j,\ C_i=a,\ C_j=b$ を満たす組の個数

ここで、$0\leq a,b<M$ です。

タイプ $2$ のクエリに対する答えは、取得した区間の情報を用いて $\displaystyle\sum_{a=0}^{M-1}\sum_{b=0}^{M-1}W_{a,b}\times pair[a][b]$ と求められます。

区間の結合を考えていきます。左側の区間の情報を $L$、右側の区間の情報を $R$ 、それらをマージした区間を $S$ とします。

各値の個数は、$S.cnt[a] = L.cnt[a] + R.cnt[a]$ と求められます。

また、条件を満たす組は次の $3$ 種類に分けられます。

• $2$ つの要素がともに左側の区間にある
• $2$ つの要素がともに右側の区間にある
• 値 $a$ の要素が左側、値 $b$ の要素が右側にある

したがって、$S.pair[a][b]$ は

$$S.pair[a][b] = L.pair[a][b] + R.pair[a][b] + L.cnt[a]\times R.cnt[b]$$

と求められます。

次に、タイプ $1$ のクエリによる区間更新を考えます。

区間内のすべての値に $x$ を加えると、値 $a$ は $(a+x)\bmod M$ に変化します。そのため、更新前のノードを $S$、更新後のノードを $S'$ とすると、各 $a,b$ について

$S'.cnt[(a+x)\bmod M]=S.cnt[a]$

$S'.pair[(a+x)\bmod M][(b+x)\bmod M]=S.pair[a][b]$

と更新できます。

つまり、$cnt$ と $pair$ の添字をそれぞれ $x$ だけ巡回させればよいです。

また、区間に $x$ を加えた後、さらに $y$ を加える操作は、初めから $(x+y)\bmod M$ を加える操作と同じです。したがって、遅延作用の合成は加算を $M$ で割った余りで管理できます。

以上の操作を適切に実装することでこの問題を解くことができます。

計算量は区間のマージと遅延作用に $O(M^2)$ 掛かることがネックになり、 $O((N+Q\log N)M^2)$です。