ABC140 E. Second Sum
問題
1からNの順列Pが与えられる。
ペア(L,R)について、P_L, ..., P_Rの中で2番目に大きいものをX_{L,R}とする。
Σ^{N-1}_{L=1} Σ^{N}_{R=L+1} X_{L,R}を求めよ。
制約
- 2 <= N <= 10^5
解法
よくある手として、あるP_iが2番目に大きいものであるような範囲を考える。
A, B, C, D > E、「・」はE以下、として、
・・・A・・・B・・・E・・・D・・・C・・・
のようになっている場合、Eが2番めに大きいものであるような範囲は、
・左側が「Bの右」から「E」まで、右側が「D」から「Cの左」までになっている範囲
・左側が「Aの右」から「B」まで、右側が「E」から「Dの左」までになっている範囲
のような感じになっている。
それぞれの範囲はその区間の個数をかけ合わせたものになるので、それらの和を求めればよい。
これをうまく実装する方法として、setを使う方法がある。
まず、setに-1を2つ、Nを2つ入れておく(ただしそのままだと重複するので、-2,-1,N,N+1にしたり、pairで異なるようにしておく)。
そして、値が大きい順に、setに入れて、その位置をfindなどで探索。そして、そのイテレータから1つ前、2つ前、1つ後、2つ後の要素のindexを取得すればよい。
