はじめに
公式ともちょっと違う上、シンプルそうなので書く。例によって数学的な証明とか言われてもわからない。
コード
当時の考察
N<10**5なので、O(N)かO(NlogN)の解法になりそう。
該当の範囲は下記4つの条件を満たしているはず。
- Xを含む範囲
- Yを含む範囲
- Xより大きい数を含まない範囲
- Yより小さい数を含まない範囲
ちょっと条件が多くてややこしい。Xより大きい数またはYより小さい数を跨ぐような範囲はあり得ないので、そういう数字は数列の区切り文字みたいな感覚で飛ばし、分割された各々の数列に対しての範囲を考えていく。こうすれば1,2のみの条件を考えればよい。
さて、対象の数列を走査して、条件を満たす範囲の数を考えてみる。
条件から、該当範囲にはXとYが含まれている。としたとき、左から4番目にXがでたあと、8番目にYの両方がでてきたとき、
???X???Y
??X???Y
?X???Y
X???Y
という感じになる。ということは、この時点で4つのパターンが満たしていることが言える。すなわち、左端からXが出てくる番号までの個数分パターンが増える、ということになる。
さて、次に来る数字について、場合分けして考えてみよう。
Xではない場合
???X???Y?
??X???Y?
?X???Y?
X???Y?
この場合でも引き続き4番目にあるXまでは左の数字を削れるので、4つのパターンを数え上げればよい。
Xの場合
???X???YX
??X???YX
?X???YX
X???YX
???YX
??YX
?YX
YX
先ほどと比べてYのある8番目まで削れるので、8つのパターンを数え上げればいい。
従い、走査している添え字までの間で最も右に来るXとYの位置を保存しておいて、どちらか小さいほうのパターン数を数え上げることができる。
あとは、冒頭に書いたX以上or以下の数字が来た時だけリセットすればよい。
計算量は線形走査するだけなのでO(N)になる。