O(N) で Minimum Sum や Second Sum を解くやつ

O(N) で Minimum Sum や Second Sum を解くやつ
誰かの提出で見てひょえ～ってなったやつ
問題リンク Minimum Sum / Second Sum
各 i について P_i が (最小値/二番目に大きい) 要素となるような区間の数や大きさを求めることができます

順列 P に対して、次の図のように L,R を取ります
(自分の1個左),(自分の1個右) を保持します

つまり、次のように矢印を張ります

これで初期化は終わりです。ここからいい感じに P_i が最小値となる区間の個数を求めていきます
P_i を大きい順に見ていくとします。例としてここでは P_2 > P_3 > P_1 > .... とします
P_2 を見ます。(自分の1個左),(自分の1個右) との index の差は 1,1 なので区間の個数は 1*1 で 1 個です
以降 P_2 はいらないので両隣の矢印を張り替えてあげます。ここが本質です
L[R[2]],R[L[2]]=L[2],R[2] のように更新します。((自分の1個右)の1個左) を (自分の1個左)にしています

P_3 を見ます。(自分の1個左) との index の差は 2 になっています。区間の個数は 2*1 で 2 個です
P_3 の両隣の矢印を張り替えます

P_1 を見ます。(自分の1個左),(自分の1個右) との index の差は 1,3 なので区間の個数は 1*3 で 3 個です
こんな感じの流れで Minimum Sum が解けます
Second Sum を解くときは、((自分の1個右)の1個右) などを調べて計算してあげます

Dancing Linksとかいうこれを二次元に拡張したアルゴリズムがあるらしい 先行研究はちゃんとしましょう

Minimum Sum を解くコードです

n = int(input())
p = list(map(int, input().split()))
memo = [0]*(n+1)
for i in range(n):
  memo[p[i]] = i+1
l = [0]+[i for i in range(n)]+[n]
r = [1]+[i+2 for i in range(n)]+[n+1]
ans = 0
for i in range(n, 0, -1):
  j = memo[i]
  ans += i * (j - l[j]) * (r[j] - j)
  l[r[j]], r[l[j]] = l[j], r[j]
print(ans)

Second Sum を解くコードです

n = int(input())
p = list(map(int, input().split()))
memo = [0]*(n+1)
for i in range(n):
  memo[p[i]] = i+1
l = [0]+[i for i in range(n)]+[n]
r = [1]+[i+2 for i in range(n)]+[n+1]
ans = 0
for i in range(1, n+1):
  j = memo[i]
  ans += i * (r[r[j]] - r[j]) * (j - l[j])
  ans += i * (l[j] - l[l[j]]) * (r[j] - j)
  l[r[j]], r[l[j]] = l[j], r[j]
print(ans)