Official

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: