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
import random
from operator import itemgetter


class RandomizedBinarySearchTree:
    def __init__(self, n):
        n += 10
        self.n = n
        self.children = [[0] * n, [0] * n]
        self.values = [0] * n
        self.counts = [0] * n
        self.indices = list(range(n - 2, -1, -1))
        self.root = -1

    def merge(self, left_root, right_root):
        children = self.children
        counts = self.counts
        li = left_root
        ri = right_root
        stack = []
        while li != -1 and ri != -1:
            if random.randrange(counts[li] + counts[ri]) < counts[li]:
                stack.append((li, 1))
                li = children[1][li]
            else:
                stack.append((ri, 0))
                ri = children[0][ri]

        i = li if li != -1 else ri
        while stack:
            pi, is_right = stack.pop()
            children[is_right][pi] = i
            counts[pi] = counts[children[0][pi]] + counts[children[1][pi]] + 1
            i = pi

        return i

    def split(self, root, x):
        i = root
        children = self.children
        values = self.values
        counts = self.counts
        l_stack = []
        r_stack = []
        while i != -1:
            if x < values[i]:
                r_stack.append(i)
                i = children[0][i]
            else:
                l_stack.append(i)
                i = children[1][i]

        li, ri = -1, -1
        while l_stack:
            pi = l_stack.pop()
            children[1][pi] = li
            counts[pi] = counts[children[0][pi]] + counts[li] + 1
            li = pi
        while r_stack:
            pi = r_stack.pop()
            children[0][pi] = ri
            counts[pi] = counts[ri] + counts[children[1][pi]] + 1
            ri = pi

        return li, ri

    def insert(self, x):
        children = self.children
        values = self.values
        counts = self.counts

        ni = self.indices.pop()
        children[0][ni] = children[1][ni] = -1
        values[ni] = x
        counts[ni] = 1

        li, ri = self.split(self.root, x)
        self.root = self.merge(self.merge(li, ni), ri)

    def delete(self, x):
        children = self.children
        counts = self.counts
        li, mri = self.split(self.root, x - 1)
        mi, ri = self.split(mri, x)

        if mi == -1:
            self.root = self.merge(li, ri)
            return

        if counts[mi] == 1:
            self.indices.append(mi)
            self.root = self.merge(li, ri)
            return

        i = mi
        stack = []
        while i != -1:
            if children[0][i] != -1 and children[1][i] != -1:
                to_right = 1 if counts[children[0][i]] < counts[children[1][i]] else 0
                stack.append((i, to_right))
                i = children[to_right][i]
            else:
                if children[0][i] != -1:
                    if stack:
                        pi, is_right = stack[-1]
                        children[is_right][pi] = children[0][i]
                    else:
                        mi = children[0][i]
                elif children[1][i] != -1:
                    if stack:
                        pi, is_right = stack[-1]
                        children[is_right][pi] = children[1][i]
                    else:
                        mi = children[1][i]
                else:
                    pi, is_right = stack[-1]
                    children[is_right][pi] = -1
                break

        self.indices.append(i)
        while stack:
            pi, _ = stack.pop()
            counts[pi] -= 1

        self.root = self.merge(self.merge(li, mi), ri)

    def upper_bound(self, x, default=-1):
        i = self.root
        children = self.children
        values = self.values
        counts = self.counts
        y = default
        c = counts[i]
        j = 0
        while i != -1:
            if x < values[i]:
                y = values[i]
                c = j + counts[children[0][i]]
                i = children[0][i]
            else:
                j += counts[children[0][i]] + 1
                i = children[1][i]
        return y, c

    def lower_bound(self, x, default=-1):
        i = self.root
        children = self.children
        values = self.values
        counts = self.counts
        y = default
        c = counts[i]
        j = 0
        while i != -1:
            if x <= values[i]:
                y = values[i]
                c = j + counts[children[0][i]]
                i = children[0][i]
            else:
                j += counts[children[0][i]] + 1
                i = children[1][i]
        return y, c

    def get_k_th(self, k, default=-1):
        i = self.root
        children = self.children
        values = self.values
        counts = self.counts
        if counts[i] <= k:
            return default
        j = k
        while i != -1:
            left_count = counts[children[0][i]]
            if left_count == j:
                return values[i]
            elif left_count > j:
                i = children[0][i]
            else:
                j -= left_count + 1
                i = children[1][i]
        return default

    def debug_print(self):
        print('Lefts ', self.children[0])
        print('Rights', self.children[1])
        print('Values', self.values)
        print('Counts', self.counts)
        self._debug_print(self.root, 0)

    def _debug_print(self, i, depth):
        if i != -1:
            self._debug_print(self.children[0][i], depth + 1)
            print('      ' * depth, self.values[i], self.counts[i])
            self._debug_print(self.children[1][i], depth + 1)


n = int(input())
ppp = list(map(int, input().split()))
pps = list(enumerate(ppp))
pps.sort(reverse=True, key=itemgetter(1))

rbst = RandomizedBinarySearchTree(n)
rbst.insert(-1)
rbst.insert(-1)
rbst.insert(n)
rbst.insert(n)

ans = 0
for i, p in pps:
    r1, j = rbst.upper_bound(i)
    r2 = rbst.get_k_th(j + 1)
    l1 = rbst.get_k_th(j - 1)
    l2 = rbst.get_k_th(j - 2)
    ans += p * ((l1 - l2) * (r1 - i) + (r2 - r1) * (i - l1))
    rbst.insert(i)
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect, insort

N = int(input())
P = list(map(int, input().split()))

ind = [-1] * (N + 1)
for i in range(N):
	ind[P[i]] = i

doneind = [-2, -1, ind[N], N, N + 1]
ans = 0
for i in range(N - 1, 0, -1):
	j = bisect(doneind, ind[i])
	if doneind[j] != N:
		ans += i * (doneind[j + 1] - doneind[j]) * (ind[i] - doneind[j - 1])
	if doneind[j - 1] != -1:
		ans += i * (doneind[j] - ind[i]) * (doneind[j - 1] - doneind[j - 2])
	insort(doneind, ind[i])
print(ans)

Submission status: Accepted

Solution code:

class BalancingTree:
    class node:
        def __init__(self, v, p):
            self.value = v
            self.pivot = p
            self.left = None
            self.right = None

    def __init__(self, n):
        self.N = n
        self.root = self.node(1 << n, 1 << n)

    def debug(self):
        def debug_info(nd_):
            return (nd_.value - 1, nd_.pivot - 1, nd_.left.value - 1 if nd_.left else -1,
                    nd_.right.value - 1 if nd_.right else -1)

        def debug_node(nd):
            re = []
            if nd.left:
                re += debug_node(nd.left)
            if nd.value: re.append(debug_info(nd))
            if nd.right:
                re += debug_node(nd.right)
            return re

        print("Debug - root =", self.root.value - 1, debug_node(self.root)[:50])

    def append(self, v):  # v を追加（その時点で v はない前提）
        v += 1
        nd = self.root
        while True:
            if v == nd.value:
                # v がすでに存在する場合に何か処理が必要ならここに書く
                return 0
            else:
                mi, ma = min(v, nd.value), max(v, nd.value)
                if mi < nd.pivot:
                    nd.value = ma
                    if nd.left:
                        nd = nd.left
                        v = mi
                    else:
                        p = nd.pivot
                        nd.left = self.node(mi, p - (p & -p) // 2)
                        break
                else:
                    nd.value = mi
                    if nd.right:
                        nd = nd.right
                        v = ma
                    else:
                        p = nd.pivot
                        nd.right = self.node(ma, p + (p & -p) // 2)
                        break

    def leftmost(self, nd):
        if nd.left: return self.leftmost(nd.left)
        return nd

    def rightmost(self, nd):
        if nd.right: return self.rightmost(nd.right)
        return nd

    def find_l(self, v):  # vより真に小さいやつの中での最大値（なければ-1）
        v += 1
        nd = self.root
        prev = 0
        if nd.value < v: prev = nd.value
        while True:
            if v <= nd.value:
                if nd.left:
                    nd = nd.left
                else:
                    return prev - 1
            else:
                prev = nd.value
                if nd.right:
                    nd = nd.right
                else:
                    return prev - 1

    def find_r(self, v):  # vより真に大きいやつの中での最小値（なければRoot）
        v += 1
        nd = self.root
        prev = 0
        if nd.value > v: prev = nd.value
        while True:
            if v < nd.value:
                prev = nd.value
                if nd.left:
                    nd = nd.left
                else:
                    if prev == 2 ** self.N:
                        return None
                    else:
                        return prev - 1
            else:
                if nd.right:
                    nd = nd.right
                else:
                    if prev == 2 ** self.N:
                        return None
                    else:
                        return prev - 1

    @property
    def find_max(self):
        return self.find_l((1 << self.N) - 1)

    @property
    def find_min(self):
        return self.find_r(-1)

    def delete(self, v, nd=None, prev=None):  # 値がvのノードがあれば削除（なければ何もしない）
        v += 1
        if not nd: nd = self.root
        if not prev: prev = nd
        while v != nd.value:
            prev = nd
            if v <= nd.value:
                if nd.left:
                    nd = nd.left
                else:
                    return
            else:
                if nd.right:
                    nd = nd.right
                else:
                    return
        if (not nd.left) and (not nd.right):
            if nd.value < prev.value:
                prev.left = None
            else:
                prev.right = None
        elif not nd.left:
            if nd.value < prev.value:
                prev.left = nd.right
            else:
                prev.right = nd.right
        elif not nd.right:
            if nd.value < prev.value:
                prev.left = nd.left
            else:
                prev.right = nd.left
        else:
            nd.value = self.leftmost(nd.right).value
            self.delete(nd.value - 1, nd.right, nd)

    def __contains__(self, v: int) -> bool:
        return self.find_r(v - 1) == v


def resolve():
    N = int(input())
    P = list(map(int, input().split()))

    A = []
    for i in range(N):
        A.append((P[i], i))

    A.sort(reverse=True)

    BT = BalancingTree(17)
    ans = 0
    for i in range(N):
        p, idx = A[i]
        BT.append(idx)

        l1 = BT.find_l(idx)  #
        l2 = BT.find_l(l1)

        r1 = BT.find_r(idx)
        if r1 is None:
            r1 = N
        r2 = BT.find_r(r1)
        if r2 is None:
            r2 = N

        cmb = (l1 - l2) * (r1 - idx) + (r2 - r1) * (idx - l1)
        ans += p * cmb

    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import os
import sys

import numpy as np


# Global variables
# N is large enough size to store nodes at one time.
# children: ndarray(N, 2)  current [left / right] child node index
# values:   ndarray(N)     -1 is represents EOT
# colors:   ndarray(N)     0:black 1:red
# counts:   ndarray(N)     number of nodes in subtree
# available: set           available indices, set(range(N)) at initial
# root:      int           root index, 0 at initial


def solve(inp):
    RBT_SIZE = 100010
    RBT_EOT = -2
    RBT_AVAILABLE_INDICES = set(range(RBT_SIZE - 1))
    RBT_CHILDREN = np.zeros((RBT_SIZE, 2), dtype=np.int64)
    RBT_VALUES = np.zeros(RBT_SIZE, dtype=np.int64)
    RBT_COLORS = np.zeros(RBT_SIZE, dtype=np.int64)
    RBT_COUNTS = np.zeros(RBT_SIZE, dtype=np.int64)
    RBT_ROOT = -1
    RBT_CHILDREN[RBT_ROOT, 0] = RBT_CHILDREN[RBT_ROOT, 1] = RBT_ROOT

    def _rbt_rotate(i, is_right):
        """
        Rotate node i to right if is_right=1 and left if 0.
        Return the index of new node that replaces node i.
        """
        r = is_right
        ci = RBT_CHILDREN[i, r ^ 1]
        RBT_CHILDREN[i, r ^ 1] = RBT_CHILDREN[ci, r]
        RBT_CHILDREN[ci, r] = i
        RBT_COLORS[ci] = RBT_COLORS[i]
        RBT_COLORS[i] = 1
        child_count = RBT_COUNTS[ci]
        RBT_COUNTS[ci] = RBT_COUNTS[i]
        RBT_COUNTS[i] -= child_count - RBT_COUNTS[RBT_CHILDREN[i, r ^ 1]]
        return ci

    def _rbt_balance_insert(i, is_right):
        flag = True
        r = is_right
        if RBT_COLORS[RBT_CHILDREN[RBT_CHILDREN[i, r], r ^ 1]] == 1:
            RBT_CHILDREN[i, r] = _rbt_rotate(RBT_CHILDREN[i, r], r)
        if RBT_COLORS[RBT_CHILDREN[RBT_CHILDREN[i, r], r]] == 1:
            if RBT_COLORS[RBT_CHILDREN[i, r ^ 1]] == 1:
                RBT_COLORS[i] = 1
                RBT_COLORS[RBT_CHILDREN[i, r]] = RBT_COLORS[RBT_CHILDREN[i, r ^ 1]] = 0
                flag = False
            else:
                i = _rbt_rotate(i, r ^ 1)
        return i, flag

    def _rbt_balance_delete(i, is_right):
        flag = True
        stack = [(i, is_right)]
        while stack:
            i, r = stack.pop()
            if RBT_COLORS[RBT_CHILDREN[RBT_CHILDREN[i, r ^ 1], r]] == 0 and \
                    RBT_COLORS[RBT_CHILDREN[RBT_CHILDREN[i, r ^ 1], r ^ 1]] == 0:
                if RBT_COLORS[RBT_CHILDREN[i, r ^ 1]] == 0:
                    RBT_COLORS[RBT_CHILDREN[i, r ^ 1]] = 1
                    if RBT_COLORS[i] == 0:
                        flag = False
                    RBT_COLORS[i] = 0
                    break
                else:
                    i = _rbt_rotate(i, r)
                    stack.append((i, r))
                    stack.append((RBT_CHILDREN[i, r], r))
                    continue
            else:
                if RBT_COLORS[RBT_CHILDREN[RBT_CHILDREN[i, r ^ 1], r]] == 1:
                    RBT_CHILDREN[i, r ^ 1] = _rbt_rotate(RBT_CHILDREN[i, r ^ 1], r ^ 1)
                i = _rbt_rotate(i, r)
                RBT_COLORS[RBT_CHILDREN[i, r]] = 0
                RBT_COLORS[RBT_CHILDREN[i, r ^ 1]] = 0
                break

        while stack:
            pi, r = stack.pop()
            RBT_CHILDREN[pi, r] = i
            i = pi

        return i, flag

    def _rbt_get_min_in_subtree(i, stack):
        while RBT_CHILDREN[i, 0] != -1:
            stack.append((i, 0))
            i = RBT_CHILDREN[i, 0]
        return i

    def rbt_insert(root, x):
        """
        Insert value x.
        Return new root index
        """

        stack = []
        i = root
        while i != -1:
            to_right = 1 if x >= RBT_VALUES[i] else 0
            stack.append((i, to_right))
            i = RBT_CHILDREN[i, to_right]

        for pi, _ in stack:
            RBT_COUNTS[pi] += 1

        i = RBT_AVAILABLE_INDICES.pop()
        RBT_CHILDREN[i, 0] = -1
        RBT_CHILDREN[i, 1] = -1
        RBT_VALUES[i] = x
        RBT_COLORS[i] = 1
        RBT_COUNTS[i] = 1

        if stack:
            pi, r = stack[-1]
            RBT_CHILDREN[pi, r] = i

        while stack:
            pi, is_right = stack.pop()
            if RBT_COLORS[pi] == 1:
                i = pi
                continue
            RBT_CHILDREN[pi, is_right] = i
            i, flag = _rbt_balance_insert(pi, is_right)

            if stack and flag:
                pi, is_right = stack.pop()
                RBT_CHILDREN[pi, is_right] = i
                break

        else:
            RBT_COLORS[i] = 0
            return i

        return root

    def rbt_delete(root, x):
        """
        Delete value x.
        Return new root index
        """
        i = root
        stack = []
        while i != -1 and RBT_VALUES[i] != x:
            is_right = 1 if RBT_VALUES[i] < x else 0
            stack.append((i, is_right))
            i = RBT_CHILDREN[i, is_right]

        if i == -1:
            return root

        if RBT_CHILDREN[i, 0] != -1 and RBT_CHILDREN[i, 1] != -1:
            stack.append((i, 1))
            mi = _rbt_get_min_in_subtree(RBT_CHILDREN[i, 1], stack)
            RBT_COLORS[i] = RBT_COLORS[mi]
            i = mi

        for pi, _ in stack:
            RBT_COUNTS[pi] -= 1

        pi, is_right = stack[-1]
        if RBT_CHILDREN[i, 0] == -1:
            RBT_CHILDREN[pi, is_right] = RBT_CHILDREN[i, 1]
            RBT_COLORS[RBT_CHILDREN[i, 1]] = 0
            if RBT_CHILDREN[i, 1] != -1 or RBT_COLORS[i] == 1:
                return root
        elif RBT_CHILDREN[i, 1] == -1:
            RBT_CHILDREN[pi, is_right] = RBT_CHILDREN[i, 0]
            RBT_COLORS[RBT_CHILDREN[i, 0]] = 0
            return root

        while stack:
            pi, is_right = stack.pop()
            i, flag = _rbt_balance_delete(pi, is_right)

            if stack and flag:
                pi, is_right = stack.pop()
                RBT_CHILDREN[pi, is_right] = i
                break

        else:
            RBT_COLORS[i] = 0
            return i

        return root

    def rbt_upper_bound(root, x):
        i = root
        y = RBT_EOT
        c = RBT_COUNTS[i]
        j = 0
        while i != -1:
            if x < RBT_VALUES[i]:
                y = RBT_VALUES[i]
                c = j + RBT_COUNTS[RBT_CHILDREN[i, 0]]
                i = RBT_CHILDREN[i, 0]
            else:
                j += RBT_COUNTS[RBT_CHILDREN[i, 0]] + 1
                i = RBT_CHILDREN[i, 1]
        return y, c

    def rbt_lower_bound(root, x):
        i = root
        y = RBT_EOT
        c = RBT_COUNTS[i]
        j = 0
        while i != -1:
            if x <= RBT_VALUES[i]:
                y = RBT_VALUES[i]
                c = j + RBT_COUNTS[RBT_CHILDREN[i, 0]]
                i = RBT_CHILDREN[i, 0]
            else:
                j += RBT_COUNTS[RBT_CHILDREN[i, 0]] + 1
                i = RBT_CHILDREN[i, 1]
        return y, c

    def rbt_get_k_th(root, k):
        i = root
        if RBT_COUNTS[i] <= k:
            return RBT_EOT
        j = k
        while i != -1:
            left_count = RBT_COUNTS[RBT_CHILDREN[i, 0]]
            if left_count == j:
                return RBT_VALUES[i]
            elif left_count > j:
                i = RBT_CHILDREN[i, 0]
            else:
                j -= left_count + 1
                i = RBT_CHILDREN[i, 1]
        return RBT_EOT

    n = inp[0]
    ppp = inp[1:]
    idx = np.argsort(ppp)[::-1]

    RBT_ROOT = rbt_insert(RBT_ROOT, -1)
    RBT_ROOT = rbt_insert(RBT_ROOT, -1)
    RBT_ROOT = rbt_insert(RBT_ROOT, n)
    RBT_ROOT = rbt_insert(RBT_ROOT, n)

    ans = 0
    for i in idx:
        p = ppp[i]
        r1, j = rbt_upper_bound(RBT_ROOT, i)
        r2 = rbt_get_k_th(RBT_ROOT, j + 1)
        l1 = rbt_get_k_th(RBT_ROOT, j - 1)
        l2 = rbt_get_k_th(RBT_ROOT, j - 2)
        ans += p * ((l1 - l2) * (r1 - i) + (r2 - r1) * (i - l1))
        RBT_ROOT = rbt_insert(RBT_ROOT, i)

    return ans


def debug_print(children, values, colors, counts, root):
    print(children.T)
    print(values)
    print(colors)
    print(counts)
    _debug_print(children, values, colors, counts, root, 0)


def _debug_print(children, values, colors, counts, i, depth):
    if i != -1:
        _debug_print(children, values, colors, counts, children[i, 0], depth + 1)
        print('      ' * depth, 'BR'[colors[i]], values[i], counts[i])
        _debug_print(children, values, colors, counts, children[i, 1], depth + 1)


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled!', file=sys.stderr)
    pass

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print(ans)

Submission status: Accepted

Solution code:
import bisect

N = int(input())
P = list(map(int, input().split()))
P_inv = [0]*N

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

c = [-1,-1, P_inv[N - 1] ,N,N]
cnt = 0
for i in reversed(range(N - 1)):
    l = bisect.bisect_left(c, P_inv[i])
    cnt += (i + 1) * ((c[l - 1] - c[l - 2]) * (c[l] - P_inv[i]) + (P_inv[i] - c[l - 1]) * (c[l + 1] - c[l]))
    bisect.insort_left(c, P_inv[i])

print(cnt)

Submission status: Accepted

Solution code:

''' 
    [Bit]
'''
class Bit:
    """ used for only int(>=0) 
        1-indexed (ignore 0-index)
    """
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
        self.depth = n.bit_length()
 
    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

    def lower_bound(self, x):
        """ 累積和がx以上になる最小のindexと、その直前までの累積和 """
        sum_ = 0
        pos = 0
        for i in range(self.depth, -1, -1):
            k = pos + (1 << i)
            if k <= self.size and sum_ + self.tree[k] < x:
                sum_ += self.tree[k]
                pos += 1 << i
        return pos + 1, sum_

    def get_less_than_x_cnt(self, x):
        """ 累積和がx未満 の個数 """
        lb_pos, lb_sum = self.lower_bound(x)
        return lb_pos-1

    def get_less_than_and_x_cnt(self, x):
        """ 累積和がx以下 の個数 """
        lb_pos, lb_sum = self.lower_bound(x+1)
        return lb_pos-1
    
    def get_more_than_x_cnt(self, x):
        """ 累積和がxより大きい 個数 """
        return self.size - self.get_less_than_and_x_cnt(x)


n = int(input())
pl = list(map(int, input().split()))
pll = []
for i,p in enumerate(pl):
    pll.append((p,i+2))

pll.sort(reverse=True)
bit = Bit(n+1)
bit.add(1,1)
ans = 0
for p,i in pll:
    ix = bit.sum(i)
    lmax, _ = bit.lower_bound(ix)
    lmin, _ = bit.lower_bound(ix-1)
    lcnt = lmax - lmin
    
    rmin, _ = bit.lower_bound(ix+1)
    rmax, _ = bit.lower_bound(ix+2)
    rcnt = rmax - rmin

    comb = lcnt*(rmin-i) + (i-lmax)*rcnt
    ans += comb*p

    bit.add(i,1)

print(ans)

Submission status: Accepted

Solution code:

''' 
    [Bit]
'''
class Bit:
    """ used for only int(>=0) 
        1-indexed (ignore 0-index)
    """
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
        self.depth = n.bit_length()
 
    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

    def lower_bound(self, x):
        """ 累積和がx以上になる最小のindexと、その直前までの累積和 """
        sum_ = 0
        pos = 0
        for i in range(self.depth, -1, -1):
            k = pos + (1 << i)
            if k <= self.size and sum_ + self.tree[k] < x:
                sum_ += self.tree[k]
                pos += 1 << i
        return pos + 1, sum_

    def get_less_than_x_cnt(self, x):
        """ 累積和がx未満 の個数 """
        lb_pos, lb_sum = self.lower_bound(x)
        return lb_pos-1

    def get_less_than_and_x_cnt(self, x):
        """ 累積和がx以下 の個数 """
        lb_pos, lb_sum = self.lower_bound(x+1)
        return lb_pos-1
    
    def get_more_than_x_cnt(self, x):
        """ 累積和がxより大きい 個数 """
        return self.size - self.get_less_than_and_x_cnt(x)


n = int(input())
pl = list(map(int, input().split()))
pll = []
for i,p in enumerate(pl):
    pll.append((p,i+1))

pll.sort(reverse=True)
bit = Bit(n)
ans = 0
for p,i in pll:
    ix = bit.sum(i)
    # print(ix)
    if ix == 0:
        lmax = 0
        lmin = 0
        lcnt = 0
    else:
        lmax, _ = bit.lower_bound(ix)
        if ix == 1:
            lmin = 0
        else:
            lmin, _ = bit.lower_bound(ix-1)
        lcnt = lmax - lmin
    
    rmin, _ = bit.lower_bound(ix+1)
    rmax, _ = bit.lower_bound(ix+2)
    rcnt = rmax - rmin

    comb = lcnt*(rmin-i) + (i-lmax)*rcnt
    ans += comb*p

    bit.add(i,1)
    # print((p,i))
    # print(lmin,lmax,i,rmin,rmax,'->',comb)
    # print()

print(ans)

Submission status: Accepted

Solution code:

def resolve():
    N = int(input())
    A = list(map(int, input().split()))

    P = [0] * (N + 1)
    for i, a in enumerate(A):
        P[a] = i

    l_idx = list(range(-1, N - 1)) + [-1, -1]
    r_idx = list(range(1, N + 1)) + [N, N]  # 番兵

    ans = 0
    for p in range(1, N + 1):
        x = P[p]

        l1 = l_idx[x]
        l2 = l_idx[l1]
        r1 = r_idx[x]
        r2 = r_idx[r1]

        cmb = (x - l1) * (r2 - r1) + (l1 - l2) * (r1 - x)
        ans += p * cmb

        l_idx[r1] = l1
        r_idx[l1] = r1

    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:

from bisect import bisect_left, bisect_right
class OrderedSet:
    def __init__(self, a):
        self.c = {}
        self.a_sort = sorted(list(set(a)))
        for i, a in enumerate(self.a_sort):
            self.c[a] = i + 1
        self.r = {v: k for k, v in self.c.items()}
        self.size = len(self.c)
        self.tree = [0] * (self.size + 1)
        self.num = [0] * self.size
        self.all_count = 0  # 全要素数

    # BITのsum関数
    def _sum(self, index):
        s = 0
        while index:
            s += self.tree[index]
            index -= index & (-index)
        return s

    # xをk個挿入する
    def insert(self, x, k=1):
        index = self.c[x]
        self.num[index - 1] += k
        while index <= self.size:
            self.tree[index] += k
            index += index & (-index)
        self.all_count += k

    # xをk個削除する
    def erase(self, x, k=1):
        self.insert(x, k=-k)

    # 格納しているxの数を返す
    def count(self, x):
        return self.num[self.c[x] - 1]

    # 下から数えてk番目の要素を返す（要素がk個未満のときNoneを返す）
    def get_kth_bottom(self, k):
        if k <= 0:
            return None
        elif self.all_count < k:
            return None
        else:
            i = 0
            s = 0
            step = 1 << (self.size.bit_length() - 1)
            while step:
                if i + step <= self.size and s + self.tree[i + step] < k:
                    i += step
                    s += self.tree[i]
                step >>= 1
            return self.r[i + 1]

    # 上から数えてk番目の要素を返す（要素がk個未満のときNoneを返す）
    def get_kth_top(self, k):
        return self.get_kth_bottom(self.all_count - k + 1)

    # x以上の最小要素を返す
    def lower_bound(self, x):
        p = bisect_left(self.a_sort, x)
        if p == 0:
            k = 1
        else:
            k = self._sum(p) + 1
        return self.get_kth_bottom(k)

    # x以下の最大要素を返す
    def upper_bound(self, x):
        p = bisect_right(self.a_sort, x)
        if p == 0:
            return None
        else:
            k = self._sum(p)
            return self.get_kth_bottom(k)


def resolve():
    N = int(input())
    A = list(map(int, input().split()))

    P = [0] * (N + 1)
    for i in range(N):
        P[A[i]] = i + 1

    OS = OrderedSet(P)
    ans = 0
    for i in range(N, 0, -1):
        p = P[i]
        c = OS.lower_bound(p)
        d = None if c is None else OS.lower_bound(c + 1)
        b = OS.upper_bound(p)
        a = None if b is None else OS.upper_bound(b - 1)

        a = a if a is not None else 0
        d = d if d is not None else N + 1

        if b is None:
            if c is not None:
                ans += i * p * (d - c)
        elif c is None:
            ans += i * (b - a) * (N - p + 1)
        else:
            ans += i * ((b - a) * (c - p) + (p - b) * (d - c))

        OS.insert(p)

    print(ans)


if __name__ == "__main__":
    resolve()