Problem:


Score : 400 points

Problem Statement

One day, Snuke was given a permutation of length N, a_1, a_2, ..., a_N, from his friend.

Find the following:

Constraints

1 ≦ N ≦ 200,000

(a_1, a_2, ..., a_N) is a permutation of (1, 2, ..., N).

Input

The input is given from Standard Input in the following format:

N
a_1 a_2 ... a_N

Output

Print the answer.

Note that the answer may not fit into a 32-bit integer.

Sample Input 1

3
2 1 3

Sample Output 1

9

Sample Input 2

4
1 3 2 4

Sample Output 2

19

Sample Input 3

8
5 4 8 1 2 6 7 3

Sample Output 3

85



Sample input:
3
2 1 3


Sample output:
9

Submission status: Accepted

Solution code:
class Avltree:

    def __init__(self, key=None):
        self.key = key
        self.left = None
        self.right = None
        self.balance = "Even"
 
    def search(self, key):
        node = self
        while node is not None:
            if node.key == key:
                return node
            if node.key > key:
                node = node.left
            elif node.key < key:
                node = node.right
        return None
 
    def search_lower(self, key, key_lower):
        node = self
        if node.key is None:
            return key_lower
        ans = key_lower
        while node is not None:
            if node.key < key:
                if ans < node.key:
                    ans = node.key
                node = node.right
            elif node.key >= key:
                node = node.left
        return ans
 
    def search_higher(self, key, key_higher):
        node = self
        if node.key is None:
            return key_higher
        ans = key_higher
        while node is not None:
            if node.key > key:
                if ans > node.key:
                    ans = node.key
                node = node.left
            elif node.key <= key:
                node = node.right
        return ans
 
 
    def end_lower(self, end_lower_key):
        node = self
        while node.left is not None:
            node = node.left
        return node.key
 
    def end_higher(self, end_higher_key):
        node = self
        while node.right is not None:
            node = node.right
        return node.key
 
 
    def DoubleRightRotation(self):
        tl = self.left
        self.left = tl.right.right
        tl.right.right = self
        tlr = tl.right
        tl.right = tlr.left
        tlr.left = tl
        if tlr.balance == "Left":
            tlr.right.balance = "Right"
            tlr.left.balance = "Even"
        elif tlr.balance == "Right":
            tlr.right.balance = "Even"
            tlr.left.balance = "Left"
        elif tlr.balance == "Even":
            tlr.right.balance = "Even"
            tlr.left.balance = "Even"
        tlr.balance = "Even"
        return tlr
    def DoubleLeftRotation(self):
        tr = self.right
        self.right = tr.left.left
        tr.left.left = self
        trl = tr.left
        tr.left = trl.right
        trl.right = tr
        if trl.balance == "Right":
            trl.left.balance = "Left"
            trl.right.balance = "Even"
        elif trl.balance == "Left":
            trl.left.balance = "Even"
            trl.right.balance = "Right"
        elif trl.balance == "Even":
            trl.left.balance = "Even"
            trl.right.balance = "Even"
        trl.balance = "Even"
        return trl
    def SingleLeftRotation(self):
        tr = self.right
        tr.balance = "Even"
        self.balance = "Even"
        self.right = tr.left
        tr.left = self
        return tr
    def SingleRightRotation(self):
        tl = self.left
        tl.balance = "Even"
        self.balance = "Even"
        self.left = tl.right
        tl.right = self
        return tl
    def replace(self, p, v):
        if p.left == self:
            p.left = v
        else:
            p.right = v
    def insert(self, key):
        if self.key is None:
            self.key = key
            return self
        if key < self.key:
            if self.left is None:
                self.left = Avltree(key)
            else:
                self.left.insertx(self, key)
        elif key > self.key:
            if self.right is None:
                self.right = Avltree(key)
            else:
                self.right.insertx(self, key)
        else:  # key == self.key:
            pass  # do not overwrite
    def insertx(self, p, key):
        node = self
        s = []
        while True:
            if node.key > key:
                s.append((node, -1))
                if node.left is None:
                    node.left = Avltree(key)
                    node = node.left
                    break
                else:
                    node = node.left
            elif node.key < key:
                s.append((node, 1))
                if node.right is None:
                    node.right = Avltree(key)
                    node = node.right
                    break
                else:
                    node = node.right
        while len(s) != 0:
            node, direct = s.pop()
            if len(s) != 0:
                par = s[-1][0]
            else:
                par = p
            if direct == -1:
                if node.balance == "Right":
                    node.balance = "Even"
                    break
                elif node.balance == "Even":
                    node.balance = "Left"
                elif node.balance == "Left":
                    if node.left.balance == "Right":
                        node.replace(par, node.DoubleRightRotation())
                    elif node.left.balance == "Left":
                        node.replace(par, node.SingleRightRotation())
                    break
            elif direct == 1:
                if node.balance == "Left":
                    node.balance = "Even"
                    break
                elif node.balance == "Even":
                    node.balance = "Right"
                elif node.balance == "Right":
                    if node.right.balance == "Left":
                        node.replace(par, node.DoubleLeftRotation())
                    elif node.right.balance == "Right":
                        node.replace(par, node.SingleLeftRotation())
                    break
 
    def to_s(self):
        return self.key
    def left_s(self):
        if self.left is None:
            return None
        return (self.left).key
    def right_s(self):
        if self.right is None:
            return None
        return (self.right).key

n=int(input())
a=list(map(int,input().split()))
ans=0
l=[0]*n
for i in range(n):
  l[a[i]-1]=i
root=Avltree()
for i in range(n):
  root.insert(l[i])
  ans+=(i+1)*(l[i]-root.search_lower(l[i],-1))*(root.search_higher(l[i],n)-l[i])
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

N = int(input())
a = [int(i) for i in input().split()]

b = [N] * N
c = [-1] * N

h = []
for i in range(N) :
    while len(h) > 0 and -h[0][0] > a[i] :
        b[h[0][1]] = i
        heappop(h)
    heappush(h, (-a[i], i))

h = []
for i in range(N - 1, -1, -1) :
    while len(h) > 0 and -h[0][0] > a[i] :
        c[h[0][1]] = i
        heappop(h)
    heappush(h, (-a[i], i))

ret = 0
for i in range(N) :
    ret += a[i] * (b[i] - i) * (i - c[i])
print(ret)

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

class BIT:

    def __init__(self, n):
        # 0-indexed
        nv = 1
        while nv < n:
            nv *= 2
        self.size = nv
        self.tree = [0] * nv

    def sum(self, i):
        """ [0, i]を合計する """
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i-1]
            i -= i & -i
        return s

    def add(self, i, x):
        """ 値の追加：添字i, 値x """
        i += 1
        while i <= self.size:
            self.tree[i-1] += x
            i += i & -i

    def get(self, l, r=None):
        """ 区間和の取得 [l, r) """
        # 引数が1つなら一点の値を取得
        if r is None: r = l + 1
        res = 0
        if r: res += self.sum(r-1)
        if l: res -= self.sum(l-1)
        return res
    
    def bisearch_left(self, l, r, x):
        """ 区間l,rで左からx番目の値がある位置 """
        l_val = self.sum(l)
        ok = r
        ng = l
        while ng+1 < ok:
            mid = (ok+ng) // 2
            if self.sum(mid) - l_val >= x:
                ok = mid
            else:
                ng = mid
        return ok

    def bisearch_right(self, l, r, x):
        """ 区間l,rで右からx番目の値がある位置 """
        r_val = self.sum(r)
        ok = r
        ng = l
        while ng+1 < ok:
            mid = (ok+ng) // 2
            if r_val - self.sum(mid) < x:
                ok = mid
            else:
                ng = mid
        return ok

N = INT()
A = LIST()
# aの昇順に処理できるようにindexで並べておく
idxs = [0] * (N+1)
for i, a in enumerate(A):
    idxs[a] = i + 1

bit = BIT(N+2)
# 先頭と末尾に番兵を仕込む
bit.add(0, 1)
bit.add(N+1, 1)
ans = [0] * (N+1)
for a in range(1, N+1):
    # a(1~N)が格納されているindex
    idx = idxs[a]
    # 自分より小さいindexで最初に自分より小さい値がある直前の場所
    l = bit.bisearch_right(-1, idx, 1) + 1
    # 自分より大きいindexで最初に自分より小さい値がある直前の場所
    r = bit.bisearch_left(idx, N+1, 1) - 1
    # aを使う回数 * a = 左端として使える範囲 * 右端として使える範囲 * a
    ans[a] = (idx-l+1) * (r-idx+1) * a
    # aを出現済とする
    bit.add(idx, 1)
# 全てのaについての合計
print(sum(ans))

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

class BIT:

    def __init__(self, n):
        # 0-indexed
        nv = 1
        while nv < n:
            nv *= 2
        self.size = nv
        self.tree = [0] * nv

    def sum(self, i):
        """ [0, i]を合計する """
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i-1]
            i -= i & -i
        return s

    def add(self, i, x):
        """ 値の追加：添字i, 値x """
        i += 1
        while i <= self.size:
            self.tree[i-1] += x
            i += i & -i

    def get(self, l, r=None):
        """ 区間和の取得 [l, r) """
        # 引数が1つなら一点の値を取得
        if r is None: r = l + 1
        res = 0
        if r: res += self.sum(r-1)
        if l: res -= self.sum(l-1)
        return res

def bisearch_min(mn, mx, func):
    """ 条件を満たす最小値を見つける二分探索 """
    ok = mx
    ng = mn
    while ng+1 < ok:
        mid = (ok+ng) // 2
        if func(mid):
            # 下を探しに行く
            ok = mid
        else:
            # 上を探しに行く
            ng = mid
    return ok

# 右から1番目の値の位置
def calc1(m):
    cnt = lend - bit.sum(m)
    return cnt < 1

# 左から1番目の値の位置
def calc2(m):
    cnt = bit.sum(m) - rstart
    return cnt >= 1

N = INT()
A = LIST()
# aの昇順に処理できるようにindexで並べておく
idxs = [0] * (N+1)
for i, a in enumerate(A):
    idxs[a] = i + 1

bit = BIT(N+2)
# 先頭と末尾に番兵を仕込む
bit.add(0, 1)
bit.add(N+1, 1)
ans = [0] * (N+1)
for a in range(1, N+1):
    # a(1~N)が格納されているindex
    idx = idxs[a]
    # 左の終点と右の始点は各回固定なので先に取っておく
    lend = bit.sum(idx)
    rstart = bit.sum(idx)
    # 自分より小さいindexで最初に自分より小さい値がある直前の場所
    l = bisearch_min(-1, idx, calc1) + 1
    # 自分より大きいindexで最初に自分より小さい値がある直前の場所
    r = bisearch_min(idx, N+1, calc2) - 1
    # aを使う回数 * a = 左端として使える範囲 * 右端として使える範囲 * a
    ans[a] = (idx-l+1) * (r-idx+1) * a
    # aを出現済とする
    bit.add(idx, 1)
# 全てのaについての合計
print(sum(ans))

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return
        
        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    

def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = [0] * (N + 1)
    for i in range(N):
        B[A[i]] = i

    uni = UnionFind(N)
    ans = 0
    for i in range(N, 0, -1):
        k = B[i]
        left = 0
        right = 0
        if k - 1 >= 0 and A[k-1] > A[k]:
            left = uni.size(uni.find(k-1))
            uni.union(k-1,k)
        if k + 1 <= N - 1 and A[k+1] > A[k]:
            right = uni.size(uni.find(k+1))
            uni.union(k+1,k)

        ans += (left+1) * (right+1) * A[k]

    print(ans)




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 18
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
A = [0] + LI() + [0]
val_ind = {A[j]: j for j in range(n + 2)}
l = {i:i - 1 for i in range(1, n + 1)}
r = {i:i + 1 for i in range(1, n + 1)}
ans = 0
for k in range(n, 0, -1):
    k_ind = val_ind[k]
    l1 = l[k_ind]
    r1 = r[k_ind]
    ans += (k_ind - l1) * (r1 - k_ind) * k
    r[l1] = r1
    l[r1] = l1



print(ans)

Submission status: Accepted

Solution code:
from bisect import*
class SquareSkipList:
    def __init__(self,values=None,sorted_=False,square=1000,seed=42):
        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<1:
                    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):
        y=self.rand_y
        y^=(y&0x7ffff)<<13
        y^=y>>17
        y^=(y&0x7ffffff)<<5
        self.rand_y=y
        if y%self.square<1:
            layer1,layer0=self.layer1,self.layer0
            idx1=bisect(layer1,x)
            layer1.insert(idx1,x)
            layer0_idx1=layer0[idx1]
            idx0=bisect(layer0_idx1,x)
            layer0.insert(idx1+1,layer0_idx1[idx0:])
            del layer0_idx1[idx0:]
        else:
            idx1=bisect(self.layer1,x)
            insort(self.layer0[idx1],x)
    def remove(self,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]
    def search_higher_equal(self,x):
        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):
        idx1=bisect(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):
        idx1=bisect_left(self.layer1,x)
        layer0_idx1=self.layer0[idx1]
        idx0=bisect_left(layer0_idx1,x)
        if idx0==0:return self.layer1[idx1-1]
        return layer0_idx1[idx0-1]
    def pop(self, idx):
        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 print(self):
        print(self.layer1)
        print(self.layer0)
def main():
    n,*a=map(int,open(0).read().split())
    l=[0]*n
    for i,v in enumerate(a,1):l[v-1]=i
    t=SquareSkipList()
    t.add(0)
    t.add(n+1)
    c=0
    for i,v in enumerate(l,1):
        c+=(t.search_higher(v)-v)*(v-t.search_lower(v))*i
        t.add(v)
    print(c)
main()

Submission status: Accepted

Solution code:
from operator import itemgetter
import sys
input = sys.stdin.readline

# 二部探索木の代わり
# max_Xが大きい場合、0を含む場合は座標圧縮する

class BITbisect():
    def __init__(self, max_X):
        self.max_X = max_X + 1
        self.bit = [0]*(self.max_X+1)

    # x番目にaを加える
    def add(self, x, a):
        while x <= self.max_X:
            self.bit[x] += a
            x += x & -x

    def insert(self, x):
        self.add(x, 1)

    def delete(self, x):
        self.add(x, -1)

    # xまでに出現している個数
    def query_sum(self, x):
        s = 0
        while x > 0:
            s += self.bit[x]
            x -= x & -x
        return s

    def exist(self, x):
        if self.query_sum(x) - self.query_sum(x-1) > 0:
            return True
        return False
    
    def count(self, x):
        return self.query_sum(x) - self.query_sum(x-1)

    # xより大きくてbitに入ってるもののうち最小のもの
    # O((logN)^2)
    def upper(self, x):
        qx = self.query_sum(x) + 1
        if qx > self.query_sum(self.max_X):
            return False
        l = 0
        r = self.max_X
        while l < r:
            m = (l+r)//2
            if self.query_sum(m) < qx:
                if l == m:
                    return r
                l = m
            else:
                r = m
        if m == self.max_X:
            return False
        return m

    # x以下でbitに入っているもののうち最大のもの
    # O((logN)^2)
    def lower(self, x):
        qx = self.query_sum(x)
        if qx == 0:
            return False
        l = 0
        r = self.max_X
        while l < r:
            m = (l+r)//2
            if self.query_sum(m) < qx:
                if l == m:
                    return r
                l = m
            else:
                r = m
        return m

    # listみたいに表示
    def display(self):
        print('inside BIT:', end=' ')
        for x in range(1, self.max_X):
            if bit.exist(x):
                c = bit.count(x)
                for _ in range(c):
                    print(x, end=' ')
        print()


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

B = []
for i, a in enumerate(A):
    B.append((i+1, a))
B.sort(key=itemgetter(1))

bit = BITbisect(N)

ans = 0
for i, a in B:
    l = bit.lower(i)
    r = bit.upper(i)
    if l is False:
        l = 0
    if r is False:
        r = N+1
    ans += (i-l)*(r-i)*a
    bit.insert(i)
print(ans)

Submission status: Accepted

Solution code:
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

    # i+1番目からR番目まで足すとt以上となるような最小のRを返す
    def bisect_plus(self, i, t):
        L = i
        R = self.size
        R_prev = R
        sum_i = self.sum(i)
        while True:
            range_sum = self.sum(R) - sum_i
            if range_sum < t:
                if R == self.size:
                    return self.size + 1
                L, R = R, R_prev
            else:
                R_prev = R
                R = (L + R + 1) // 2
                if R == R_prev:
                    return R

    # L番目からi-1番目まで足すとt以上となるような最小のRを返す
    def bisect_minus(self, i, t):
        L = 1
        R = i
        L_prev = L
        sum_i = self.sum(i - 1)
        while True:
            range_sum = sum_i - self.sum(L - 1)
            if range_sum < t:
                if L == 1:
                    return 0
                L, R = L_prev, L
            else:
                L_prev = L
                L = (L + R) // 2
                if L == L_prev:
                    return L


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

idx = [0] * (N+1)
for i in range(N):
    idx[a[i]] = i+1

bit = Bit(N)
ans = 0
for i in range(1, N+1):
    p = idx[i]
    bit.add(p, 1)
    L = bit.bisect_minus(p, 1)
    R = bit.bisect_plus(p, 1)
    ans += (((R-L) * (R-L-1)) // 2 - ((p-L) * (p-L-1)) // 2 - ((R-p) * (R-p-1)) // 2) * i

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#AGC5 B

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
lst = [0 for i in range(n+1)]
for i in range(n):
    lst[a[i]] = i

l = [0]*n
r = [0]*n
ans = 0
for i in range(1,n+1)[::-1]:
    x = lst[i]
    if x + 1 < n and a[x+1] > i:
        R = r[x+1]
    else:
        R = x
    if x - 1 >= 0 and a[x-1] > i:
        L = l[x-1]
    else:
        L = x
    l[R] = L
    r[L] = R
    ans += (x - L + 1)*(R - x + 1)*i
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int, input().split()))
E = [(v, i + 1) for i, v in enumerate(a)]
E.sort(reverse = True)
L = [0] + [i for i in range(N + 1)]
R = [i + 1 for i in range(N + 1)] + [N + 1]
res = 0
for v, i in E:
  l = L[i]
  r = R[i]
  L[r], R[l] = l, r
  res += v * (i - l) * (r - i)
print(res)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self,size):
        self.table=[-1]*size
    def root(self,x):
        while self.table[x]>=0:
            x=self.table[x]
        return x
    def unite(self,x,y):
        s1=self.root(x)
        s2=self.root(y)
        if s1!=s2:
            if self.table[s1]>self.table[s2]:
                s1,s2=s2,s1
            self.table[s1]+=self.table[s2]
            self.table[s2]=s1
        return
    def same(self,x,y):
        return self.root(x)==self.root(y)
    def size(self,x):
        return -self.table[self.root(x)]
n,*a=map(int,open(0).read().split())
u=UnionFind(n)
b=[0]*n
for i,t in enumerate(a):b[t-1]=i
c=0
for k in b[::-1]:
    l=r=1
    if k>0 and a[k-1]>a[k]:
        l+=u.size(k-1)
        u.unite(k-1,k)
    if k+1<n and a[k+1]>a[k]:
        r+=u.size(k+1)
        u.unite(k+1,k)
    c+=l*r*a[k]
print(c)

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 search_lower(self,key):
        if not key:return None
        ret=None
        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 search_higher(self,key):
        if not key:return None
        ret=None
        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,*a=map(int,open(0).read().split())
    l=[0]*n
    for i,v in enumerate(a,1):l[v-1]=i
    t=SqrtSet()
    t.insert(0)
    t.insert(n+1)
    c=0
    for i,v in enumerate(l,1):
        c+=(t.search_higher(v)-v)*(v-t.search_lower(v))*i
        t.insert(v)
    print(c)
main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from bisect import*
class BTreeNode:
    def __init__(self):self.key,self.child=[],[]
class BTree:
    def __init__(self):self.root=BTreeNode()
    def search_higher(self,key):
        ptr=self.root
        ret=None
        while ptr.child:
            i=bisect(ptr.key,key)
            if i!=len(ptr.key):ret=ptr.key[i]
            ptr=ptr.child[i]
        i=bisect(ptr.key,key)
        if i!=len(ptr.key):ret=ptr.key[i]
        return ret
    def search_lower(self,key):
        ptr=self.root
        ret=None
        while ptr.child:
            i=bisect_left(ptr.key,key)
            if i:ret=ptr.key[i-1]
            ptr=ptr.child[i]
        i=bisect_left(ptr.key,key)
        if i:ret=ptr.key[i-1]
        return ret
    def insert(self,key):
        def insert_rec(ptr):
            b_size=256
            if not ptr.child:
                insort(ptr.key,key)
                if len(ptr.key)==b_size*2-1:
                    ret=BTreeNode()
                    ret.key=ptr.key[:b_size]
                    ptr.key=ptr.key[b_size:]
                    return ret
            else:
                i=bisect(ptr.key,key)
                tmp=insert_rec(ptr.child[i])
                if tmp:
                    ptr.key.insert(i,tmp.key.pop())
                    ptr.child.insert(i,tmp)
                    if len(ptr.child)==b_size*2:
                        ret=BTreeNode()
                        ret.child=ptr.child[:b_size]
                        ptr.child=ptr.child[b_size:]
                        ret.key=ptr.key[:b_size]
                        ptr.key=ptr.key[b_size:]
                        return ret
        tmp=insert_rec(self.root)
        if tmp:
            root=BTreeNode()
            root.key=[tmp.key.pop()]
            root.child=[tmp,self.root]
            self.root=root
def main():
    n,*a=map(int,open(0).read().split())
    l=[0]*n
    for i,v in enumerate(a,1):l[v-1]=i
    t=BTree()
    insert,search_higher,search_lower=t.insert,t.search_higher,t.search_lower
    insert(0)
    insert(n+1)
    c=0
    for i,v in enumerate(l,1):
        c+=(search_higher(v)-v)*(v-search_lower(v))*i
        insert(v)
    print(c)
main()

Submission status: Accepted

Solution code:
from bisect import*
class BTreeNode:
    def __init__(self):self.key,self.child=[],[]
class BTree:
    def __init__(self):self.root=BTreeNode()
    def search_higher(self,key):
        ptr=self.root
        ret=None
        while ptr.child:
            i=bisect(ptr.key,key)
            if i!=len(ptr.key):ret=ptr.key[i]
            ptr=ptr.child[i]
        i=bisect(ptr.key,key)
        if i!=len(ptr.key):ret=ptr.key[i]
        return ret
    def search_lower(self,key):
        ptr=self.root
        ret=None
        while ptr.child:
            i=bisect_left(ptr.key,key)
            if i:ret=ptr.key[i-1]
            ptr=ptr.child[i]
        i=bisect_left(ptr.key,key)
        if i:ret=ptr.key[i-1]
        return ret
    def insert(self,key):
        def insert_rec(ptr):
            b_size=256
            if not ptr.child:
                insort(ptr.key,key)
                if len(ptr.key)==b_size*2-1:
                    ret=BTreeNode()
                    ret.key=ptr.key[:b_size]
                    ptr.key=ptr.key[b_size:]
                    return ret
            else:
                i=bisect(ptr.key,key)
                tmp=insert_rec(ptr.child[i])
                if tmp:
                    ptr.key.insert(i,tmp.key.pop())
                    ptr.child.insert(i,tmp)
                    if len(ptr.child)==b_size*2:
                        ret=BTreeNode()
                        ret.child=ptr.child[:b_size]
                        ptr.child=ptr.child[b_size:]
                        ret.key=ptr.key[:b_size]
                        ptr.key=ptr.key[b_size:]
                        return ret
        tmp=insert_rec(self.root)
        if tmp:
            root=BTreeNode()
            root.key=[tmp.key.pop()]
            root.child=[tmp,self.root]
            self.root=root
def main():
    n,*a=map(int,open(0).read().split())
    l=[0]*n
    for i,v in enumerate(a,1):l[v-1]=i
    t=BTree()
    t.insert(0)
    t.insert(n+1)
    c=0
    for i,v in enumerate(l,1):
        c+=(t.search_higher(v)-v)*(v-t.search_lower(v))*i
        t.insert(v)
    print(c)
main()