序
公式解説及びユーザー解説がとても上手いやり方なので、今回の自分の解法は参考程度になります。
（ユーザー解説の方は理解しきれていない部分もあるので自分のアルゴリズムと似た構造を持っている可能性はあります）
初投稿でQiitaの使い方もままならないです。もうしわけない。
解き方
概要
条件を満たす部分配列について考える問題です。
ある数Xが含まれる部分配列の個数を$I(X)$とすれば、XとYを含む部分配列は以下のように書けます。
$$ I(X \land Y) = I(X \lor Y) - I(X) - I(Y)$$
今回はこれを解きます。
具体的に
それでは内容に入ります。まず、公式解説のほうにもありましたが、Xより大きい、Yより小さい要素が存在する部分配列は、絶対に条件を満たさないので、この要素がある場合にはその前とその後の配列を別々に考えます。
なので、XやYを超えるものがない配列について考えます。
10 3 1
3 2 1 2 2 2 1 2 1 2
このとき、X及びYのインデックスについて考えます。（今回はインデックスを1から開始しています）
$$ind(X) = [1]$$ $$ ind(Y) = [3, 7, 9]$$ $$ind(X \lor Y) = [1, 3, 7, 9]$$
また、部分配列は$(L,R)$の形で表すことにします。上の例のときは、$(1,3) = [3,2,1]$のため、条件を満たす部分配列になります。
さて、インデックス集合Aに含まれるインデックス要素のうち、少なくとも1つが出現する部分配列の個数を$I_{index}(A)$とし、まずインデックスが1つの場合について考えます。
その前に、N=10の場合の全部分配列を列挙しておきます。(考えられる全てのインデックスのいずれかを含めば良いので、$I_{index}(\{1,2,\dots,10\})$)
- $I_{index}(\{1,2,\dots,10\})$
L=1 : (1,1), (1,2), (1,3), (1,4), (1,5), (1,6), (1,7), (1,8), (1,9), (1,10)
L=2 : (2,2), (2,3), (2,4), (2,5), (2,6), (2,7), (2,8), (2,9), (2,10)
L=3 : (3,3), (3,4), (3,5), (3,6), (3,7), (3,8), (3,9), (3,10)
L=4 : (4,4), (4,5), (4,6), (4,7), (4,8), (4,9), (4,10)
L=5 : (5,5), (5,6), (5,7), (5,8), (5,9), (5,10)
L=6 : (6,6), (6,7), (6,8), (6,9), (6,10)
L=7 : (7,7), (7,8), (7,9), (7,10)
L=8 : (8,8), (8,9), (8,10)
L=9 : (9,9), (9,10)
L=10: (10,10)
数え上げると$I_{index}(\{1,2,\dots,10\}) = 55$ですが、$\frac{1}{2} 10 (10 + 1)$で計算自体はできます。
インデックスが1つの場合
- $I_{index}(\{1\})$
L=1 : (1,1), (1,2), (1,3), (1,4), (1,5), (1,6), (1,7), (1,8), (1,9), (1,10)
上記のみなので、$I_{index}(\{1\}) = 10$となります。
- $I_{index}(\{2\})$
L=1 : (1,2), (1,3), (1,4), (1,5), (1,6), (1,7), (1,8), (1,9), (1,10)
L=2 : (2,2), (2,3), (2,4), (2,5), (2,6), (2,7), (2,8), (2,9), (2,10)
上記のみなので、$I_{index}(\{2\}) = 18$となります。
- $I_{index}(\{3\})$
L=1 : (1,3), (1,4), (1,5), (1,6), (1,7), (1,8), (1,9), (1,10)
L=2 : (2,3), (2,4), (2,5), (2,6), (2,7), (2,8), (2,9), (2,10)
L=3 : (3,3), (3,4), (3,5), (3,6), (3,7), (3,8), (3,9), (3,10)
上記のみなので、$I_{index}(\{3\}) = 24$となります。法則性が見えてきました。
- $I_{index}(\{3\})$
L=1 : (1,4), (1,5), (1,6), (1,7), (1,8), (1,9), (1,10)
L=2 : (2,4), (2,5), (2,6), (2,7), (2,8), (2,9), (2,10)
L=3 : (3,4), (3,5), (3,6), (3,7), (3,8), (3,9), (3,10)
L=4 : (4,4), (4,5), (4,6), (4,7), (4,8), (4,9), (4,10)
上記のみなので、$I_{index}(\{4\}) = 28$となります。
このため、一般化すると、$I_{index}(\{a\}) = (N- a + 1) \times a$
インデックスが複数の場合
思考過程では、$2,3\dots$と増やしていきましたが、実際法則性は$2,3\dots$でも変化しないので一気に駆け抜けます。
- $I_{index}(\{1, 2\})$
L=1 : (1,1), (1,2), (1,3), (1,4), (1,5), (1,6), (1,7), (1,8), (1,9), (1,10)
L=2 : (2,2), (2,3), (2,4), (2,5), (2,6), (2,7), (2,8), (2,9), (2,10)
インデックス$1$か$2$を含む場合は簡単で、$2$が含まれる場合に$(1,1)$を足したものが答えになります。つまり、
$I_{index}(\{1, 2\})=18+1$
- $I_{index}(\{2,3\})$
L=1 : (1,2), (1,3), (1,4), (1,5), (1,6), (1,7), (1,8), (1,9), (1,10)
L=2 : (2,2), (2,3), (2,4), (2,5), (2,6), (2,7), (2,8), (2,9), (2,10)
L=3 : (3,3), (3,4), (3,5), (3,6), (3,7), (3,8), (3,9), (3,10)
インデックス$2$か$3$を含む場合も簡単です。$3$が含まれる場合を起点として、$(1,2)$と$(2,2)$を足すだけです。つまり、
$I_{index}(\{2, 3\})=24 + 2$
法則性が見えてきそうです。
- $I_{index}(\{1, 2, 3\})$
L=1 : (1,1), (1,2), (1,3), (1,4), (1,5), (1,6), (1,7), (1,8), (1,9), (1,10)
L=2 : (2,2), (2,3), (2,4), (2,5), (2,6), (2,7), (2,8), (2,9), (2,10)
L=3 : (3,3), (3,4), (3,5), (3,6), (3,7), (3,8), (3,9), (3,10)
$I_{index}(\{1, 2, 3\})=24+1+2$ですね。$24$はもちろん$I_{index}(\{3\})$です。
$I_{index}(\{a, b, c\}) = I_{index}(\{c\}) + a + b \,\,(a < b< c)$になりそうです。
- $I_{index}(\{1, 3\})$
L=1 : (1,1), (1,2), (1,3), (1,4), (1,5), (1,6), (1,7), (1,8), (1,9), (1,10)
L=2 : (2,3), (2,4), (2,5), (2,6), (2,7), (2,8), (2,9), (2,10)
L=3 : (3,3), (3,4), (3,5), (3,6), (3,7), (3,8), (3,9), (3,10)
$I_{index}(\{1, 3\}) = 24 + 2$ ... ん？法則性からいくと$+1$のはず……。
- $I_{index}(\{2, 4\})$
L=1 : (1,2), (1,3), (1,4), (1,5), (1,6), (1,7), (1,8), (1,9), (1,10)
L=2 : (2,2), (2,3), (2,4), (2,5), (2,6), (2,7), (2,8), (2,9), (2,10)
L=3 : (3,4), (3,5), (3,6), (3,7), (3,8), (3,9), (3,10)
L=4 : (4,4), (4,5), (4,6), (4,7), (4,8), (4,9), (4,10)
$I_{index}(\{2, 4\}) = 28 + 4$ $\dots 4$！？
はい、賢い方はお気づきの通り、逆です。$(L,R)$の$R \ge 4$について考えると、当然$28$個になるので、これ以外について考えます。まず、$L=1$について、インデックスに$2$が含まれれば良いので、$(1,2)$と$(1,3)$が追加されます。これは、$(4-2)$コ追加されます。$L=2$も同様で、$(4-2)$コ追加されます。
大体わかってきた気がしますが、最後に$I_{index}(\{1,3, 4\})$をやってみます。
- $I_{index}(\{1,3, 4\})$
L=1 : (1,1), (1,2), (1,3), (1,4), (1,5), (1,6), (1,7), (1,8), (1,9), (1,10)
L=2 : (2,3), (2,4), (2,5), (2,6), (2,7), (2,8), (2,9), (2,10)
L=3 : (3,3), (3,4), (3,5), (3,6), (3,7), (3,8), (3,9), (3,10)
L=4 : (4,4), (4,5), (4,6), (4,7), (4,8), (4,9), (4,10)
数え上げると$I_{index}(\{1,3, 4\}) = 33$となります。さっきと同じように、$(L,R)$の$R < 4$について考えます。$L=3$では$(4-3)$コ、$L=2$でも$(4-3)$コ、$L=1$で$(4-1)$コ、追加されるので、$28 + 1 + 1 + 3 = 33$となります。
結局どうゆうことなの？
$I_{index}(\{1,3, 4\})$についてもう一度考えます。
まず$I_{index}(\{4\})$について数え上げます。
$\{1,3, 4\}$から$4$を取り除きます。
残りのインデックス集合は$\{1,3\}$となります。
$L=4 ～1$を調べます。
$L=i$のとき、残りのインデックス集合から、$i$以上を満たす最小のインデックス$k$を見つけます。
足し上げる数として、$4-k$を書きだします。
$L=4$: $k$はないのでスキップ
$L=3$: $k = 3$、ゆえに$4-k = 1$
$L=2$: $k = 3$、ゆえに$4-k = 1$
$L=1$: $k = 1$、ゆえに$4-k = 3$
これを$I_{index}(\{4\})$に足すので、$I_{index}(\{1,3, 4\}) = I_{index}(\{4\}) + 1 + 1 + 3 = 33$となり、上のときと同じ結論を得られました。
アルゴリズム
$I_{index}(A)$を求めます。
$ans = I_{index}(max(A))$
$B = A - \{max(A)\}$
for i is max(A) to 1:
min_ = max(A)
for e in B:
if e >= i and min_
min_=e
ans = ans + (max(A) - min_)
For文を回したくない。
上のアルゴリズムでは、$max(A)$回ループするのでこれを避けたいです。そもそも、インデックスを書いていくときにはリストに追加していく形式なので、必ず昇順です。
$I_{index}(\{1,3, 4\})$について考えてみると、$I_{index}(\{1,3, 4\}) = I_{index}(\{4\}) + (4 - 3) \times 2 + (4-1)\times1$となっています。
これはいくつかさらに試すとわかりますが、
$I_{index}(\{a,b,c\}) = I_{index}(\{c\}) + (c - b) \times (b-a) + (c-a)\times (a-0) \,\,(a < b <c) $
となっています。4つ以上のときも同じで、$a_1 < a_2 < \dots < a_n$について、$a_0 = 0$とすれば、
$$I_{index}(\{a_1 < a_2 <\dots < a_n\}) = I_{index}(\{a_n\}) + \sum_{i=n}^{1} (a_n - a_i) \times (a_i - a_{i-1}) $$
これで、ループを$a_n$回から$n$回までに減らせます。