Problem:


Score: 500 points

Problem Statement

Given is a permutation P of \{1, 2, \ldots, N\}.

For a pair (L, R) (1 \le L \lt R \le N), let X_{L, R} be the second largest value among P_L, P_{L+1}, \ldots, P_R.

Find \displaystyle \sum_{L=1}^{N-1} \sum_{R=L+1}^{N} X_{L,R}.

Constraints

 2 \le N \le 10^5 

 1 \le P_i \le N 

 P_i \neq P_j  (i \neq j)

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
P_1 P_2 \ldots P_N

Output

Print \displaystyle \sum_{L=1}^{N-1} \sum_{R=L+1}^{N} X_{L,R}.

Sample Input 1

3
2 3 1

Sample Output 1

5

X_{1, 2} = 2, X_{1, 3} = 2, and X_{2, 3} = 1, so the sum is 2 + 2 + 1 = 5.

Sample Input 2

5
1 2 3 4 5

Sample Output 2

30

Sample Input 3

8
8 2 7 3 4 5 6 1

Sample Output 3

136



Sample input:
3
2 3 1


Sample output:
5

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

"""
PiがX_LRに選ばれる時の通り数を考える
左右それぞれに，自分より大きいものが出てくる場所を近い順に2箇所上げておけば良い．

これを計算するにはPの大きい順に見ていき，L=[]にインデックスを追加していく．bisectで新しく見たやつのindexの挿入かっしょを調べて左右を見る
=>要素の追加がうまくできない，seg木 or マルチセット
"""

def main():

    ##############################
    from bisect import bisect_left, bisect_right, insort_right
    class SquareSkipList:
        # SkipList の層数を 2 にした感じの何か
        # std::multiset の代用になる

        def __init__(self, values=None, sorted_=False, square=1000, seed=42):
            # values: 初期値のリスト
            # sorted_: 初期値がソート済みであるか
            # square: 最大データ数の平方根
            # seed: 乱数のシード
            ### pop関数は　for を回すので重め、使うなら square パラメータを大きめにするべき

            self.cnt=0#要素数を持っておくか
            inf = float("inf")
            self.square = square
            if values is None:
                self.rand_y = seed
                self.layer1 = [inf]
                self.layer0 = [[]]
            else:
                self.layer1 = layer1 = []
                self.layer0 = layer0 = []
                if not sorted_:
                    values.sort()
                y = seed
                l0 = []
                for v in values:
                    y ^= (y & 0x7ffff) << 13
                    y ^= y >> 17
                    y ^= (y & 0x7ffffff) << 5
                    if y % square == 0:
                        layer0.append(l0)
                        l0 = []
                        layer1.append(v)
                    else:
                        l0.append(v)
                layer1.append(inf)
                layer0.append(l0)
                self.rand_y = y

        def add(self, x):  # 要素の追加  # O(sqrt(n))
            # xorshift
            y = self.rand_y
            y ^= (y & 0x7ffff) << 13
            y ^= y >> 17
            y ^= (y & 0x7ffffff) << 5
            self.rand_y = y

            if y % self.square == 0:
                layer1, layer0 = self.layer1, self.layer0
                idx1 = bisect_right(layer1, x)
                layer1.insert(idx1, x)
                layer0_idx1 = layer0[idx1]
                idx0 = bisect_right(layer0_idx1, x)
                layer0.insert(idx1+1, layer0_idx1[idx0:])  # layer0 は dict で管理した方が良いかもしれない  # dict 微妙だった
                del layer0_idx1[idx0:]
            else:
                idx1 = bisect_right(self.layer1, x)
                insort_right(self.layer0[idx1], x)

            self.cnt+=1#追加

        def remove(self, x):  # 要素の削除  # O(sqrt(n))
            # x が存在しない場合、x 以上の最小の要素が削除される
            idx1 = bisect_left(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                del self.layer1[idx1]
                self.layer0[idx1] += self.layer0.pop(idx1+1)
            else:
                del layer0_idx1[idx0]

            self.cnt-=1

        def search_higher_equal(self, x):  # x 以上の最小の値を返す  O(log(n))
            idx1 = bisect_left(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                return self.layer1[idx1]
            return layer0_idx1[idx0]

        def search_higher(self, x):  # x を超える最小の値を返す  O(log(n))
            idx1 = bisect_right(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_right(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                return self.layer1[idx1]
            return layer0_idx1[idx0]

        def search_lower(self, x):  # x 未満の最大の値を返す  O(log(n))
            #x未満のものがない場合，infが返るかも！！！  
            idx1 = bisect_left(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == 0:  # layer0_idx1 が空の場合とすべて x 以上の場合
                return self.layer1[idx1-1]
            return layer0_idx1[idx0-1]

        def pop(self, idx):
            # 小さい方から idx 番目の要素を削除してその要素を返す（0-indexed）
            # O(sqrt(n))
            # for を回すので重め、使うなら square パラメータを大きめにするべき
            self.cnt-=1
            layer0 = self.layer0
            s = -1
            for i, l0 in enumerate(layer0):
                s += len(l0) + 1
                if s >= idx:
                    break
            if s==idx:
                layer0[i] += layer0.pop(i+1)
                return self.layer1.pop(i)
            else:
                return layer0[i].pop(idx-s)


        def all(self):
            print(self.layer1)
            print(self.layer0)

        def len(self):
            return self.cnt

    ##############################


    import bisect
    
    mod=10**9+7
    N=I()
    P=LI()
    from collections import defaultdict
    dd = defaultdict(int)
    
    for i in range(N):
        P[i]=[P[i],i]
        
    P.sort(reverse=True)
    
    ssl = SquareSkipList(square=2000)#見たやつのindexを持っておく，初期値は番兵
    ssl.add(-2)
    ssl.add(-1)
    ssl.add(N)
    ssl.add(N+1)
    
    ans=0
    for i in range(N):
        p=P[i][0]
        index=P[i][1]
        l1=ssl.search_lower(index)
        l2=ssl.search_lower(l1)
        r1=ssl.search_higher(index)
        r2=ssl.search_higher(r1)
        
        #端の処理
        if l2==-2:
            l2=-1
        if r2==N+1:
            r2=N
        
        a=l1-l2
        b=index-l1
        c=r1-index
        d=r2-r1
        
        ssl.add(index)
        
        temp=a*c + b*d
        ans+=temp*p
        
    print(ans)
        
        
        
            
    
    

main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
P = list(map(int,input().split()))

A = [[P[i], i] for i in range(len(P))]
A.sort(reverse=True)
# print(A)

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
  
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
  
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

B = Bit(n+1)
L0 = [[0] * 2 for i in range(n)]
for i in range(n):
    ind = A[i][1]
    B.add(ind+1, 1)
    s = B.sum(ind+1)
    R = [-1, -1]
    for j in range(2):
        l = -1
        r = ind+1
        m = (l+r+1)//2
        while r-l > 1:
            if B.sum(m) < s-1-j:
                l = m
            else:
                r = m
            m = (l+r+1)//2
        R[j] = r
    L0[i] = [ind+1-R[0], R[0]-R[1]]
    # print(i, ind, R, L0[i])

# print(L)
    
B = Bit(n+1)
L1 = [[0] * 2 for i in range(n)]
for i in range(n):
    ind = n-1-A[i][1]
    B.add(ind+1, 1)
    s = B.sum(ind+1)
    R = [-1, -1]
    for j in range(2):
        l = -1
        r = ind+1
        m = (l+r+1)//2
        while r-l > 1:
            if B.sum(m) < s-1-j:
                l = m
            else:
                r = m
            m = (l+r+1)//2
        R[j] = r
    L1[i] = [ind+1-R[0], R[0]-R[1]]
    # print(i, ind, R, L1[i])

# print(L0,L1)
ans = 0
for i in range(n):
    ans += (n-i) * (L0[i][0] * L1[i][1] + L0[i][1] * L1[i][0])
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N = I()
A = IL()

P = [None for i in range(N)]
for i in range(N):
  P[A[i]-1] = i

R = DD(lambda:N)
L = DD(lambda:-1)
R2 = DD(lambda:N)
L2 = DD(lambda:-1)

stack = []
stack2 = []
for i in range(N):
  while stack2 and stack2[-1]<A[i]:
    R2[stack2.pop()-1] = i
  temp = []
  while stack and stack[-1]<A[i]:
    a = stack.pop()
    R[a-1] = i
    temp.append(a)
  while temp:
    stack2.append(temp.pop())
  stack.append(A[i])
  
stack = []
stack2 = []
for i in range(N)[::-1]:
  while stack2 and stack2[-1]<A[i]:
    L2[stack2.pop()-1] = i
  temp = []
  while stack and stack[-1]<A[i]:
    a = stack.pop()
    L[a-1] = i
    temp.append(a)
  while temp:
    stack2.append(temp.pop())
  stack.append(A[i])

ans = 0
for i in range(N):
  a,b,c,d,e = L2[i],L[i],P[i],R[i],R2[i]
  ans += ((c-b)*(e-d) + (b-a)*(d-c))*(i+1)
print(ans)

Submission status: Accepted

Solution code:
from bisect import*
class SqrtSet:
    def __init__(self,block_limit=201):
        self.key=[]
        self.child=[[]]
        self.block_limit=block_limit
    def le(self,key):
        ret=key
        i=bisect_left(self.key,key)
        if i:ret=self.key[i-1]
        block=self.child[i]
        i=bisect_left(block,key)
        if i:ret=block[i-1]
        return ret
    def ge(self,key):
        ret=key
        i=bisect(self.key,key)
        if i<len(self.key):ret=self.key[i]
        block=self.child[i]
        i=bisect(block,key)
        if i<len(block):ret=block[i]
        return ret
    def insert(self,key):
        i=bisect(self.key,key)
        block=self.child[i]
        insort(block,key)
        if len(block)==self.block_limit:
            sep=self.block_limit//2
            self.key.insert(i,block[sep])
            self.child.insert(i+1,block[sep+1:])
            self.child[i]=block[:sep]
def main():
    n,*p=map(int,open(0).read().split())
    l=[0]*n
    for i,v in enumerate(p,1):l[v-1]=i
    t=SqrtSet()
    insert,le,ge=t.insert,t.le,t.ge
    insert(0),insert(n+1)
    a=0
    for i,v in list(enumerate(l,1))[::-1]:
        f,b=ge(v),le(v)
        g,c=ge(f),le(b)
        a+=i*((f-v)*(b-c)+(v-b)*(g-f))
        insert(v)
    print(a)
main()

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
p = list(map(lambda x: int(x)-1, input().split()))

def init(bit, values):
    for i,v in enumerate(values):
        add(bit,i+1,v)
#a1 ~ aiまでの和 O(logn)
def query(bit,i):
    res = 0
    while i > 0:
        res += bit[i]
        i -= i&(-i)
    return res

#ai += x(logN)
def add(bit,i,x):
    if i==0:
        raise RuntimeError
    while i <= len(bit)-1:
        bit[i] += x
        i += i&(-i)
    return

def index(bit, v):
    """a1,...,aiの和がv以上になる最小のindexを求める
    存在しないとき配列サイズを返す
    """
    i = 0
    n = len(bit)-1
    k = 1<<((n-1).bit_length())
#     k = 1
#     while 2*k<n:
#         k *= 2
    while k>0:
        if i+k<n+1 and bit[i+k]<v:
            v -= bit[i+k]
            i += k
        k //= 2
    if v==1:
        return i+1
    else:
        return n+1

ind = [None]*n
for i,num in enumerate(p):
    ind[num] = i
bit = [0]*(n+1)
l = [None]*n
l2 = [None]*n
r = [None]*n
r2 = [None]*n
for num in range(n-1, -1, -1):
    i = query(bit, ind[num])
    if i==0:
        l[ind[num]] = -1
        l2[ind[num]] = -1
    elif i==1:
        l[ind[num]] = index(bit, i) - 1
        l2[ind[num]] = -1
    else:
        l[ind[num]] = index(bit, i) - 1
        l2[ind[num]] = index(bit, i-1) - 1
    r[ind[num]] = index(bit, i+1) - 1
    r2[ind[num]] = index(bit, i+2) - 1
    add(bit, ind[num]+1, 1)

    
ans = 0
for i, (num, li, li2, ri, ri2) in enumerate(zip(p, l, l2, r, r2)):
    v = 0
    if li>=0:
        v += (ri-i)*(li-li2)
    if ri<n:
        v += (i-li)*(ri2-ri)
#     print(i,li,li2, ri, ri2,v)
    ans += v * (num+1)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N = int(input())
P = [None] + [int(x) for x in input().split()]
p_to_i = [None] * (N+1)
for i,x in enumerate(P[1:],1):
    p_to_i[x] = i

# 大きい数から挿入していく
# 左隣にあるインデックスを取得できるようにしておく
# そのために、[1,i]内で書き込んだ数の個数を獲得できるBITを持つ

# BITは一番最後の1ビットの位置が重要なので0ではなく1始まり。そのためNまでループする
def BIT_add(i):
    while i <= N:
        tree[i] += 1
        i += i&(-i)

def BIT_sum(i):
    s = 0
    while i:
        s += tree[i]
        i -= i&(-i)
    return s

def BIT_search(x):
    # 二分探索。和がx以上となる最小のインデックス(>= 1)を返す
    i = 0
    s = 0
    step = 1<<(N.bit_length()-1)
    while step:
        if i+step <= N and s + tree[i+step] < x:
            i += step
            s += tree[i]
        step >>= 1
    return i+1
    left = 0
    right = N
    while right - left > 1:
        mid = (left + right) // 2
        if BIT_sum(mid) >= x:
            right = mid
        else:
            left = mid
    return right

tree = [0] * (N+1)
answer = 0
for x in range(N,0,-1):
    c = p_to_i[x]
    L = BIT_sum(c) # 左にある既に書き込んだ数の個数
    BIT_add(c)
    R = N-x-L # 右にある既に書き込んだ数の個数
    a = BIT_search(L-1) if L >= 2 else 0
    b = BIT_search(L) if L >= 1 else 0
    d = BIT_search(L+2) if R >= 1 else N+1
    e = BIT_search(L+3) if R >= 2 else N+1
    coef = 0
    if b != 0:
        # [b,c]を含むようにする。(a,b) と(c,d)が自由
        coef += (b-a) * (d-c)
    if d != 0:
        # [c,d]を含むようにする。
        coef += (e-d) * (c-b)
    answer += x * coef
print(answer)

Submission status: Accepted

Solution code:

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N = int(input())
P = [None] + [int(x) for x in input().split()]
p_to_i = [None] * (N+1)
for i,x in enumerate(P[1:],1):
    p_to_i[x] = i

# 大きい数から挿入していく
# 左隣にあるインデックスを取得できるようにしておく
# そのために、[1,i]内で書き込んだ数の個数を獲得できるBITを持つ

# BITは一番最後の1ビットの位置が重要なので0ではなく1始まり。そのためNまでループする
def BIT_add(i):
    while i <= N:
        tree[i] += 1
        i += i&(-i)

def BIT_sum(i):
    s = 0
    while i:
        s += tree[i]
        i -= i&(-i)
    return s

def BIT_search(x):
    # 二分探索。和がx以上となる最小のインデックス(>= 1)を返す
    # i = 0
    # s = 0
    # step = 1<<(N.bit_length()-1)
    # while step:
    #     if i+step <= N and s + tree[i+step] < x:
    #         i += step
    #         s += tree[i]
    #     step >>= 1
    # return i+1
    left = 0
    right = N
    while right - left > 1:
        mid = (left + right) // 2
        if BIT_sum(mid) >= x:
            right = mid
        else:
            left = mid
    return right

tree = [0] * (N+1)
answer = 0
for x in range(N,0,-1):
    c = p_to_i[x]
    L = BIT_sum(c) # 左にある既に書き込んだ数の個数
    BIT_add(c)
    R = N-x-L # 右にある既に書き込んだ数の個数
    a = BIT_search(L-1) if L >= 2 else 0
    b = BIT_search(L) if L >= 1 else 0
    d = BIT_search(L+2) if R >= 1 else N+1
    e = BIT_search(L+3) if R >= 2 else N+1
    coef = 0
    if b != 0:
        # [b,c]を含むようにする。(a,b) と(c,d)が自由
        coef += (b-a) * (d-c)
    if d != 0:
        # [c,d]を含むようにする。
        coef += (e-d) * (c-b)
    answer += x * coef
print(answer)