\(A\) における要素の重複を無視して単純に集合とみなしたものを \(S\) とします．

クエリでの変更後に \(S=\{0,1,\dots,M-1\}\) であるとき答えは \(MK\) です． またクエリでの変更前に \(S=\{0,1,\dots,M-1\}\) かつ変更後に \(S=\{0,1,\dots,M-1\}\setminus\{x\}\) となったとき，答えは \(\sum_{k=0}^{K-1}(Ck+x)\bmod M\) でこれは floor sum を利用すれば高速に計算できます．

クエリでの変更前後ともに \(S\neq\{0,1,\dots,M-1\}\) であるとき，\(S\) を円環上の極大な区間に分割して考えることができます． 区間 \(I=\{x \bmod M\mid l\leq x\lt r \}\ (r-l\leq M-1)\) を考えると，\(k\) が \(0\in \{(Ck+x)\bmod M\mid x\in I\}\) をみたすときは答えに \((Ck+r)\bmod M\) だけ寄与し，そうでないときの寄与は \(0\) です． \(r-l\leq M-1\) に注意すれば，\(I\) の答えへの寄与は以下の形で書くことができます．

\[\sum_{k=0}^{K-1}\left(\left\lfloor\frac{Ck+r-1}{M}\right\rfloor-\left\lfloor\frac{Ck+l-1}{M}\right\rfloor\right)\left((Ck+r)\bmod M\right)(=:f(l,r))\]

この値そのものも一般化 floor sum を用いれば計算できますが，クエリ前後での差分を考えると \(l\leq x\lt r\leq l+M-1\) を満たす整数 \(l,x,r\) に対して \(f(l,r)-f(l,x)-f(x+1,r)\) の値が計算できれば十分であり，整理すると以下のように（一般化でない）floor sum で計算できる形になります．

\[ \begin{aligned} &f(l,r)-f(l,x)-f(x+1,r)\\ &=\sum_{k=0}^{K-1}\left(\left\lfloor\frac{Ck+r-1}{M}\right\rfloor-\left\lfloor\frac{Ck+l-1}{M}\right\rfloor\right)\left((Ck+r)\bmod M\right)\\ &\quad-\sum_{k=0}^{K-1}\left(\left\lfloor\frac{Ck+x-1}{M}\right\rfloor-\left\lfloor\frac{Ck+l-1}{M}\right\rfloor\right)\left((Ck+x)\bmod M\right)\\ &\quad-\sum_{k=0}^{K-1}\left(\left\lfloor\frac{Ck+r-1}{M}\right\rfloor-\left\lfloor\frac{Ck+x}{M}\right\rfloor\right)\left((Ck+r)\bmod M\right)\\ &\overset{(\star)}=\sum_{k=0}^{K-1}\left(\left\lfloor\frac{Ck+x}{M}\right\rfloor-\left\lfloor\frac{Ck+l-1}{M}\right\rfloor\right)\left((Ck+r)\bmod M-(Ck+x)\bmod M\right)\\ &=\sum_{k=0}^{K-1}\left(\left\lfloor\frac{Ck+x}{M}\right\rfloor-\left\lfloor\frac{Ck+l-1}{M}\right\rfloor\right)\left(r-x-\left(\left\lfloor\frac{Ck+r}{M}\right\rfloor-\left\lfloor\frac{Ck+x}{M}\right\rfloor\right)M\right)\\ &\overset{(\star\star)}=\sum_{k=0}^{K-1}\left(\left\lfloor\frac{Ck+x}{M}\right\rfloor-\left\lfloor\frac{Ck+l-1}{M}\right\rfloor\right)\left(r-x\right) \end{aligned} \]

ただし \((\star)\) では

\[ \left\lfloor\frac{Ck+x-1}{M}\right\rfloor((Ck+x)\bmod M) =\left\lfloor\frac{Ck+x}{M}\right\rfloor((Ck+x)\bmod M) \]

であることを，\((\star\star)\) では \(l\leq x\lt r\leq l+M-1\) より

\[ \left(\left\lfloor\frac{Ck+x}{M}\right\rfloor-\left\lfloor\frac{Ck+l-1}{M}\right\rfloor\right) \left(\left\lfloor\frac{Ck+r}{M}\right\rfloor-\left\lfloor\frac{Ck+x}{M}\right\rfloor\right) =0 \]

であることを用いています．

実装例(C++)

なお円環上の区間を管理する必要がありますが，基本的には \([0,M)\) 上で通常の区間管理を行い，ある要素を含むような極大区間を取得する際にのみ \(0,M\) を跨ぐことを考慮することにすれば実装しやすく，既存のライブラリの流用も行いやすいです．