解説なし
問題文の読み違えで、全ての要素が以上の部分列を求めると勘違いしており、解けませんでした。
部分列の問題では各が必ず末尾に付くような部分列を考えていくと、重複を避けて数え上げることができます。今回もその方法で解くことができます。
具体例として、、
を末尾とする部分列を考えます。
問題の条件から、部分列の先頭がである部分列の末尾を
にできます。
また、例えば、という部分列について、間
の選び方は自由に決定できるので、できる部分列は全部で
通りあります。
同様に、では
通り、
では
通りの部分列ができます。
したがって、を末尾とする部分列は全部で、
通りあります。
一般化すると、が末尾となる部分列は、
かつ
を満たすような
について、
を計算することで求めることができます。
では、その計算方法を考えます。
・
である
に関する値
の総和を求める
まず、具体例で考えると、を末尾にすることを考えているとき、
としておくと、
を満たすのは、
の時なので、
とすることで部分列の総数が求まります。
しかし、今回、毎回条件を満たすを調べることはできません。
このように、既に出現したようなものであって、かつ、その中のある値以下の総和をとりたいとき、Binary Index Tree(BIT)によって計算できます。
配列を
とします。
これは、である
について
が記録されています。
このの
の和が
となって目的の値が計算できます。
(蟻本のBITによる反転数の求め方と同じ理屈です)
今回の問題では、であるため、そのままだと配列に記録できません。そのため、座標圧縮する必要があります。
・iから離れると増加する2の冪乗の計算
が2から4まで遷移する時の
の動きを確認します。
このように、が1つ進むと、
より前の2の指数は全て+1されます。
を進める度に
である
全てに2をかけていては
となり計算量的に間に合いません。
このような時に使えるのが、2の逆元の冪乗を記録していく方法です。具体例ののときを例にします。
を記録しておくと、
となり、ここに
を掛けることで、求めたい値が得られます。
このようにすると、2の冪乗と2の逆元の冪乗を保存する変数を用意しておき、が+1されるたびにそれらに
、
を掛けていくだけでよくなります。
ちなみに、式で考えると
となり、上記計算と同じになります。
BITでの計算はなので、全体の計算量は
です。
提出コード:https://atcoder.jp/contests/abc221/submissions/26376907