geam1113’s diary

主にAtcoderのコンテストの備忘録を書きます。AtCoder緑と水色を行ったり来たりしています。

ABC221E LEQ

部分列問題 ABC BIT

解説なし

問題文の読み違えで、全ての要素が $A_1'$ 以上の部分列を求めると勘違いしており、解けませんでした。

部分列の問題では各 $A_i$ が必ず末尾に付くような部分列を考えていくと、重複を避けて数え上げることができます。今回もその方法で解くことができます。

具体例として、
$A=\{ 2, 1, 9, 3, 10, 8, 7, 6, 5, 4\}$ 、 $A_9=5$ を末尾とする部分列を考えます。

問題の条件から、部分列の先頭が $A_1, A_2, A_4$ である部分列の末尾を $A_9$ にできます。

また、例えば、 $\{A_2,...,A_9\}$ という部分列について、間 $A_3,...,A_8$ の選び方は自由に決定できるので、できる部分列は全部で $2^{6}$ 通りあります。

同様に、 $A_1$ では $2^7$ 通り、 $A_4$ では $2^4$ 通りの部分列ができます。

したがって、 $A_9$ を末尾とする部分列は全部で、 $2^7+2^6+2^4$ 通りあります。

一般化すると、 $A_i$ が末尾となる部分列は、 $j \lt i$ かつ $A_j \leq A_i$ を満たすような $j_1,...,j_m$ について、 $2^{i-j_1-1}+...+2^{i-j_m-1}$ を計算することで求めることができます。

では、その計算方法を考えます。

・ $A_j \leq A_i$ である $A_j$ に関する値 $V_{A_j}$ の総和を求める

まず、具体例で考えると、 $A_9$ を末尾にすることを考えているとき、 $B=\{2^7,\ 2^6,\ 2^5,\ 2^4,\ 2^3,\ 2^2,\ 2^1,\ 2^0\}$ としておくと、 $A_j \leq A_9$ を満たすのは、 $j=1,2,4$ の時なので、 $B_1+B_2+B_4$ とすることで部分列の総数が求まります。

しかし、今回、毎回条件を満たす $j$ を調べることはできません。

このように、既に出現したようなものであって、かつ、その中のある値以下の総和をとりたいとき、Binary Index Tree(BIT)によって計算できます。

配列 $V$ を $V=\{2^6,\ 2^7,\ 2^4,\ 0,\ 0,\ 2^0,\ 2^1, \ 2^2,\ 2^5,\ 2^3\}$ とします。

これは、 $i \lt 9$ である $A_i,B_i$ について $V_{A_i}=B_i$ が記録されています。

この $V$ の $[1,5]$ の和が $V_1+V_2+V_3+V_4+V_5=2^6+2^7+2^4$ となって目的の値が計算できます。

（蟻本のBITによる反転数の求め方と同じ理屈です）

今回の問題では、 $A_i \leq 10^9$ であるため、そのままだと配列に記録できません。そのため、座標圧縮する必要があります。

・iから離れると増加する2の冪乗の計算

$i$ が2から4まで遷移する時の $B$ の動きを確認します。

$i=2,\ B=\{2^0\}$
$i=3,\ B=\{2^1,2^0\}$

$i=4,\ B=\{2^2,2^1,2^0\}$

このように、 $i$ が１つ進むと、 $i$ より前の2の指数は全て+1されます。

$i$ を進める度に $j \lt i$ である $j$ 全てに2をかけていては $O(N^2)$ となり計算量的に間に合いません。

このような時に使えるのが、2の逆元の冪乗を記録していく方法です。具体例の $i=9$ のときを例にします。

$B=\{2^{-1},\ 2^{-2},\ 2^{-3},\ 2^{-4},\ 2^{-5},\ 2^{-6},\ 2^{-7},\ 2^{-8}\}$ を記録しておくと、

$B_1+B_2+B_4=2^{-1}+2^{-2}+2^{-4}$ となり、ここに $2^8$ を掛けることで、求めたい値が得られます。

このようにすると、2の冪乗と2の逆元の冪乗を保存する変数を用意しておき、 $i$ が+1されるたびにそれらに $2$ 、 $2^{-1}$ を掛けていくだけでよくなります。

ちなみに、式で考えると

$2^{i-j_1-1}+...+2^{i-j_m-1}=(2^{-j_1}+...+2^{-j_m}) \times 2^{i-1}$ となり、上記計算と同じになります。

BITでの計算は $O(logN)$ なので、全体の計算量は $O(NlogN)$ です。

提出コード:https://atcoder.jp/contests/abc221/submissions/26376907