まずはクエリが無い場合を考えます．以下が成立します．

• \((1, 2)\) として使われる \(1\) は， \((0, 1)\) として使われる \(1\) より前にあるとしてよい．

（証明）ある最大マッチングにおいて，\(A=(\dots,0, \ldots,1_A,\ldots,1_B,\ldots,2\ldots)\) が \((0, 1_A), (1_B,2)\) というマッチングがあったとき， \((0, 1_B), (1_A,2)\) というマッチングに置き換えられるため．（証明終）

マッチングに含むことができる \((i, i+1)\) の最大値を \(B_i\) ，\(A\) に含まれる \(i\) の個数を \(C_i\) とし，マッチングで使われる \((i, i+1)\) の個数を \(x_i\) とすると， \(x_0,\ldots,x_{M-1}\) は以下を満たす必要があります．

• 条件 1. : \(0\leq x_i\leq B_i\) （ \((i, i+1)\) をマッチングに入れることができる条件）
• 条件 2. : \(x_{i-1}+x_i\leq C_i\) （ \(A\) に含まれる \(i\) の個数の条件 ）

上の二つの条件を満たすうえで \(\sum x\) を最大化すればよいです．すなわち，以下の整数計画問題が解ければよいです．

\[ \mathrm{maximize} \sum_{i=0}^{M-1}x_i\ \ \mathrm{subject\ to}\ 0\leq x_i\leq B_i\land x_{i-1}+x_i\leq C_i\]

（整数計画問題の制約）

• \(0\leq B_i\leq \min(C_i,C_{i+1})\)
• \(0\leq C_i\)
• \(\sum C=N\)

ここで \(x_0\) を固定して残りの \(x_1,x_2,\ldots,x_{M-1}\) をこの順に貪欲に決めていったときの \(\sum x\) を \(g(x_0)\) とすると， \(g(x_0)=\min(x_0+p,q,-x_0+r)\) の形で表すことができます（証明は別ページ）．したがって \(g(0)\) および \(g(B_0)\) を求められれば，\(g(x_0)\) が最大となる \(x_0\) が分かるのでこの問題は \(O(M)\) で解くことができます．

クエリごとに \(B,C\) を高速に求めます．\(C\) の更新は自明なので \(B\) の更新を考えます．

\(B\) の更新について，各 \(i=0,1,\ldots,M-1\) について \(i\) と \(i+1\) が登場する場所をあらかじめ列挙して座圧をしておくと，各 \(i\) について次の問題を高速に解ければよくなります．

• 012 からなる文字列がある．連続とは限らない 12 の部分列を同時に最大いくつ選べるか？ 一点更新のクエリがたくさん与えられるので高速に処理せよ．（\(0\) は \(i,i+1\) どちらでもないこと，\(1\) は \(i\) であること，\(2\) は \(i+1\) であることを表しています．）

これは segment tree を用いれば一点更新や答えの取得を \(O(\log |S|)\) （\(S\) は文字列の長さ）で求めることができます．

各クエリによって \(B\) の値を再計算しなければならないのは高々 \(4\) 箇所なので，各クエリに対して \(O(\log (N+Q))\) で \(B\) を更新することができます．

よって，この問題を \(O((N+Q)\log(N+Q)+QM)\) で解くことができます．