B - Matching Query Editorial
by
toam
部分点解法
まずはクエリが無い場合を考えます.以下が成立します.
- \((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)\) で解くことができます.
posted:
last update: