数式の意味は、全てのLとRの組み合わせにおけるを足し込めということです。
方針
全ての(L,R)の組み合わせにおいてある値iが何回『二番目に大きい数』となるか、が分かれば良いのでその方針で解いていきます。
考察
ある値iが二番目に大きい数かどうかを判定するのには、iよりも大きい数のインデックスが重要となっていきます。なぜなら、iよりも大きい数が(L,R)の範囲内に1つのみ含まれていないと行けないからです。
更に進めると、必要なのはiよりも大きい数字で、左右それぞれ二番目に近いインデックスの値が必要となります。
これは、とりあえず例を考えてみましょう。
例
入力例3の(8 2 7 3 4 5 6 1)で、考えてみます。
たとえば、ある数を4とした場合、気にする必要がある数字が4つ出てきます。
- 4より大きいかつ、4から見て左側にある2番目に近い数字 8
- 4より大きいかつ、4から見て左側にある1番目に近い数字 7
- 4より大きいかつ、4から見て右側にある1番目に近い数字 5
- 4より大きいかつ、4から見て右側にある2番目に近い数字 6
4が『2番目に大きい数』になる組み合わせを全て列挙すると(L,R)={(2,5),(3,5),(4,6),(5,6)}です。
順列の数字にすると(2-4)(7-4)(3-5)(4-5)となります。
この色の意味は、赤色の組み合わせはiより大きい数が左側にある場合(すなわち7を含む場合)と、iより大きい数が右側にある場合(すなわち5を含む場合)です。
実際には、ある数字をi,ある数字のインデックスを,それぞれの4つの数字のインデックスを上から
とした時に、何回『二番目に大きい数になるか』は
となります。
上の画像で言うと左項は赤字、右項は青字です。また、と
はそれぞれにおいてLの取れる組み合わせ、
と
はRの取れる組み合わせとなっています。
このようにある値が『二番目に大きい数字』になるかは、上記4つの数字を考えれば良いことがわかります。
たとえば、今回の入力例が(8 2 7 3 4 5 6 1 9)になったとしても、組み合わせの数は増減しませんね。
実装
要は、上記の4つの数字を調べれば良いのですが、これを愚直に求めようとすると毎回かかってしまい、全体の計算量は
でとても間に合いません。
今回は、multisetとupper_boundを利用していきます。
multisetは重複を許す組み合わせです。今回はインデックスの管理に使います。upper_boundは、ある数xより大きい数字の入ったset内のイテレータをで検索してくれます。
これを使っていくため、今回は大きい数字から検索していきます。ある数字iの『二番目に大きい数字』となる回数が計算し終わったら、そのiのインデックスをmultisetに挿入していきます。そして次はi-1を見る…としていくと、multisetの中には常にiよりも大きい数のインデックスのみが入っている状態となります。あとはこれを利用して、イテレータを使って辿っていくと4つの数字にたどり着く事が出来ます。
ただし、適当に実装すると面倒な場合分けが多くなります。なので、multisetに予め番兵として0とn+1を2つずつ入れておくと実装が楽になります。(1-indexedにした場合です,0-indexedなら-1とn)
