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:
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def maximal_rectangle(H):
    """ヒストグラムに対して、極大長方形を計算。
    各 i に対して、[l,r) が高さ H[i] となるような l, r を計算する。
    アリ本 p.299～p.300
    """
    N = len(H)
    L = np.empty(N, np.int32)
    R = np.empty(N, np.int32)
    st = np.zeros(N, np.int32)
    # 左端の計算
    t = 0
    for i in range(N):
        while t and H[st[t - 1]] >= H[i]:
            t -= 1
        L[i] = 0 if t == 0 else st[t - 1] + 1
        st[t] = i
        t += 1
    # 右端の計算
    t = 0
    for i in range(N - 1, -1, -1):
        while t and H[st[t - 1]] >= H[i]:
            t -= 1
        R[i] = N if t == 0 else st[t - 1]
        st[t] = i
        t += 1
    return L, R

signature = '(i8[:],)'
if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('maximal_rectangle', signature)(maximal_rectangle)
    cc.compile()

from my_module import maximal_rectangle

A = np.array(read().split(), np.int64)[1:]

N = len(A)
L, R = maximal_rectangle(A)
coef = (np.arange(N) - L + 1) * (R - np.arange(N))
x = np.sum(coef * A)
print(x)

Submission status: Accepted

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

class SegTree():
    # 1-indexed
    def __init__(self, N, function, basement):
        self.n = N
        self.K = (self.n-1).bit_length()
        self.f = function
        self.b = basement
        self.seg = [basement]*(2**(self.K+1)+1)

    def update(self, k, value):
        X = 2**self.K
        k += X
        self.seg[k] = value
        while k:
            k = k >> 1
            self.seg[k] = self.f(self.seg[k << 1], self.seg[(k << 1) | 1])

    def query(self, L, R):
        num = 2**self.K
        L += num
        R += num
        vL = self.b
        vR = self.b
        while L < R:
            if L & 1:
                vL = self.f(vL, self.seg[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.f(self.seg[R], vR)
            L >>= 1
            R >>= 1
        return self.f(vL, vR)

    def find_max_index(self, L, R, X):
        # [L,R)でX以下の物で最大indexを取得
        return self.fMi(L, R, X, 1, 0, 2**self.K)

    def find_min_index(self, L, R, X):
        # [L,R) でX以下の物で最小のindexを取得する
        return self.fmi(L, R, X, 1, 0, 2**self.K)

    def fMi(self, a, b, x, k, l, r):
        if self.seg[k] > x or r <= a or b <= l:
            return -1
        else:
            if k >= 2**self.K:
                return k-2**self.K
            else:
                vr = self.fMi(a, b, x, (k << 1) | 1, (l + r) // 2, r)
                if vr != -1:
                    return vr
                return self.fMi(a, b, x, k << 1, l, (l + r) // 2)

    def fmi(self, a, b, x, k, l, r):
        if self.seg[k] > x or r <= a or b <= l:
            return -1
        else:
            if k >= 2**self.K:
                return k-2**self.K
            else:
                vl = self.fmi(a, b, x, k << 1, l, (l+r)//2)
                if vl != -1:
                    return vl
                return self.fmi(a, b, x, k << 1 | 1, (l+r)//2, r)

def main():
    N = int(input())
    A = list(map(int, input().split()))
    seg = SegTree(N, min, N+1)
    B = [0]*N
    for i, v in enumerate(A):
        B[i] = (i, A[i])
    B.sort(key=lambda x: x[1])
    ans = 0
    for index, v in B:
        seg.update(index, 1)
        left = seg.find_max_index(0, index, 1)
        right = seg.find_min_index(index+1, N, 1)
        if right == -1:
            right = N
        ans += v*(index-left)*(right-index)
    print(ans)
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split()))

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

ans = 0
L = Bit(n)
R = Bit(n)

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

    ind = B[i][2]+1
    l = 0
    r = ind+1
    m = (l+r)//2
    rind = R.sum(ind)
    while r-l>1:
        if R.sum(m) < rind:
            l = m
        else:
            r = m
        m = (l+r)//2
    b = l
    R.add(ind+1, 1)

    ans += (i+1) * (B[i][1]+1 - a) * (n+1-b - (B[i][1]+1))
    # print(i+1, B[i][1]+1, a, n+1-b, ans)


print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():
    N = int(input())
    A = list(enumerate(map(int,input().split())))
    A.sort(key = lambda x:-x[1])

    left = list(range(-1,N + 2))
    right = list(range(1,N + 4))
    ans = 0
    for i,a in A:
        L = left[i]
        R = right[i]
        ans += a*(i - L)*(R - i)
        left[R] = L
        right[L] = R
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class SegmentTree:
    def __init__(self, array, operator, identity_element):
        _len = len(array)
        self.__op = operator
        self.__size = 1 << (_len - 1).bit_length()
        self.__tree = [identity_element] * self.__size + \
            array + [identity_element] * (self.__size - _len)
        self.__ie = identity_element

        for i in range(self.__size - 1, 0, -1):
            self.__tree[i] = operator(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def update(self, i, v):
        i += self.__size
        self.__tree[i] = v
        while i:
            i //= 2
            self.__tree[i] = self.__op(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def query(self, l, r):
        """[l, r)
        """
        l += self.__size
        r += self.__size
        ret = self.__ie
        while l < r:
            if l & 1:
                ret = self.__op(ret, self.__tree[l])
                l += 1
            if r & 1:
                r -= 1
                ret = self.__op(ret, self.__tree[r])
            l //= 2
            r //= 2
        return ret


@mt
def slv(N, A):
    ai = [(a, i) for i, a in enumerate(A)]
    ai.sort()

    lst = SegmentTree([-1] * N, max, -1)
    rst = SegmentTree([N] * N, min, N)
    ans = 0
    for a, i in ai:
        l = lst.query(0, i)
        r = rst.query(i+1, N)
        ans += (i-l) * (r-i) * a
        lst.update(i, i)
        rst.update(i, i)
    return ans


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def main():
	
	# SegmentTree Class
	class SegmentTree:
		
		# 初期化
		def __init__(self, size, default):
			self.size = 2**(size-1).bit_length()
			self.default = default
			self.seg = [default]*(2*self.size-1)

		# function(max, min, plus, minus, etc...)
		def segfunc(self,x,y):
			return max(x,y)

		# update
		def update(self,k,x):
			k += self.size-1
			self.seg[k] = x
			while k:
				k = (k-1)//2
				self.seg[k] = self.segfunc(self.seg[2*k+1],self.seg[2*k+2])

		# query([p,q)のsegfunc)
		def query(self,p,q):
			if q <= p:
				return self.default
			p += self.size-1;q += self.size-2
			ret = self.default
			while q-p > 1:
				if p&1 == 0:
					ret = self.segfunc(ret,self.seg[p])
				if q&1 == 1:
					ret = self.segfunc(ret,self.seg[q])
					q -= 1
				p = p//2
				q = (q-1)//2
			ret = self.segfunc(self.segfunc(ret,self.seg[p]),self.seg[q])
			return ret

		# seg確認用
		def seg_print(self):
			print(self.seg)
		
	N = int(input())
	a = list(map(int,input().split()))
	ans=[i+1 for i in range(N)]
	left_seg = SegmentTree(N, 0)
	for i, num in enumerate(a):
	    ans[num-1] *= i + 1 - left_seg.query(0,num)
	    left_seg.update(num-1, i+1)
	right_seg = SegmentTree(N, 0)
	for i, num in enumerate(a[::-1]):
	    ans[num-1] *= i + 1 - right_seg.query(0,num)
	    right_seg.update(num-1, i+1)
	
	print(sum(ans))

if __name__ == "__main__":
	main()

Submission status: Accepted

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

def main():
	
	class BinaryIndexedTree:
		
		# 初期化
		def __init__(self, size, default):
			self.size = size
			self.default = default
			self.BIT = [default]*(self.size+1)

		# function(max, min, plus, minus, etc...)
		def BIT_segfunc(self, x, y):
			return max(x, y)

		def BIT_query(self, idx):
			ret = self.default
			while idx > 0:
				ret = self.BIT_segfunc(ret, self.BIT[idx])
				idx -= idx&(-idx)
			return ret

		# update
		def BIT_update(self, idx, x):
			while idx <= self.size:
				self.BIT[idx] = self.BIT_segfunc(self.BIT[idx], x)
				idx += idx&(-idx)
			return

		def BIT_range(self, x, y):
			return self.BIT_query(y)-self.BIT_query(x)

		# seg確認用
		def BIT_print(self):
			print(self.BIT)
		
	N = int(input())
	a = list(map(int,input().split()))
	l = [0]*N;r = [0]*N
	left_bit = BinaryIndexedTree(N, 0)
	for i, num in enumerate(a):
	    l[num-1] = i + 1 - left_bit.BIT_query(num)
	    left_bit.BIT_update(num, i+1)
	right_bit = BinaryIndexedTree(N, 0)
	for i, num in enumerate(a[::-1]):
	    r[num-1] = i + 1 - right_bit.BIT_query(num)
	    right_bit.BIT_update(num, i+1)
	
	print(sum(l[i]*r[i]*(i+1) for i in range(N)))

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
# B - Minimum Sum
N = int(input())
A = list(enumerate(list(map(int,input().split()))))
left = [i-1 for i in range(N)]
right = [i+1 for i in range(N)]
A.sort(key=lambda x:x[1],reverse=True)
ans = 0
for i,a in A:
    il,ir = left[i],right[i]
    ans += a*(i-il)*(ir-i)
    if ir<N:
        left[ir] = il
    if il>-1:
        right[il] = ir
print(ans)

Submission status: Accepted

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

B = [0] * (N + 1)
l = [i for i in range(N + 2)]
r = [i for i in range(N + 2)]

ans = 0
for i in range(N):
    B[A[i]] = i

for i in range(N, 0, -1):
    m = B[i]
    x, y = l[m], r[m]
    ans += i * (m - x + 1) * (y - m + 1)
    l[y + 1], r[x - 1] = x, y

print(ans)

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    a = [(int(x),i+1) for i,x in enumerate(sys.stdin.readline().split())]

    N0 = 2**(N.bit_length())
    st1 = [0] * (2*N0)
    st2 = [N+1] * (2*N0)

    def update_max(i,x):
        i += N0 - 1
        st1[i] = x
        while i > 0:
            i = (i-1) // 2
            st1[i] = max(st1[i*2+1],st1[i*2+2])

    def update_min(i,x):
        i += N0 - 1
        st2[i] = x
        while i > 0:
            i = (i-1) // 2
            st2[i] = min(st2[i*2+1],st2[i*2+2])

    def query_max(l,r):
        L = l + N0; R = r + N0
        ret = 0
        while L < R:
            if L % 2:
                ret = max(ret,st1[L-1])
                L += 1
            if R % 2:
                R -= 1
                ret = max(ret,st1[R-1])
            L //= 2; R //=2
        return ret

    def query_min(l,r):
        L = l + N0; R = r + N0
        ret = N+1
        while L < R:
            if L % 2:
                ret = min(ret,st2[L-1])
                L += 1
            if R % 2:
                R -= 1
                ret = min(ret,st2[R-1])
            L //= 2; R //= 2
        return ret

    a.sort()
    ans = 0
    for x,y in a:
        i = query_max(1,y)
        j = query_min(y,N+1)
        ans += (y-i) * (j-y) * x
        update_max(y,y)
        update_min(y,y)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class BinaryIndexedTree:
    # http://hos.ac/slides/20140319_bit.pdf
    def __init__(self, size):
        """
        :param int size:
        """
        self.bit = [0 for _ in range(size)]
        self.size = size

    def add(self, i, w):
        """
        i番目にwを加える
        :param int i:
        :param int w:
        :return:
        """
        x = i + 1
        while x <= self.size:
            self.bit[x - 1] += w
            x += x & -x
        return

    def sum(self, i):
        """
        [0,i]の合計
        :param int i:
        :return:
        """
        res = 0
        x = i + 1
        while x > 0:
            res += self.bit[x - 1]
            x -= x & -x
        return res

    def search(self, x):
        """
        二分探索。和がx以上となる最小のインデックス(>= 1)を返す
        :param int x:
        :return :
        """
        i = 0
        s = 0
        step = 1 << self.size.bit_length()
        while step:
            if i + step <= self.size and s + self.bit[i + step - 1] < x:
                print(self.bit[i + step - 1], i, step)
                i += step
                s += self.bit[i - 1]
            step >>= 1
        return i

    def __len__(self):
        return self.size
from collections import defaultdict
n=int(input())
a=list(map(int,input().split()))
d=defaultdict(int)
for i in range(n):
  d[a[i]]=i+1
Bit = BinaryIndexedTree(n+1)
ans=0
for i in range(n):
  j=i+1
  i=d[j]
  x=Bit.sum(i)
  ok=i
  ng=-1
  while ok - ng > 1:
    mid=(ok+ng)//2
    if Bit.sum(mid)==x:
      ok=mid
    else:
      ng=mid
  l=ok+1
  ok=i
  ng=n+1
  while ng - ok > 1:
    mid=(ok+ng)//2
    if Bit.sum(mid)==x:
      ok=mid
    else:
      ng=mid
  r=ok
  ans+=j*(i-l+1)*(r-i+1)
  Bit.add(i,1)
print(ans)

Submission status: Accepted

Solution code:
class BinaryIndexedTree(): #1-indexed
    def __init__(self, n):
        self.n = n
        self.tree = [0 for _ in range(n + 1)]

    def sum(self, idx):
        res = 0
        while idx:
            res += self.tree[idx]
            idx -= idx & -idx
        return res

    def get(self, idx):
        return self.sum(idx) - self.sum(idx - 1)

    def add(self, idx, x):
        while idx <= self.n:
            self.tree[idx] += x
            idx += idx & -idx

    def bisect_left(self, x):
        if x <= 0: return 0
        res, tmp = 0, 2**((self.n).bit_length() - 1)
        while tmp:
            if res + tmp <= self.n and self.tree[res + tmp] < x:
                x -= self.tree[res + tmp]
                res += tmp
            tmp >>= 1
        if res >= self.n:
            return self.n
        return res + 1

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

D = [None for _ in range(N)]

for i in range(N):
    D[A[i] - 1] = i + 1

bit = BinaryIndexedTree(N + 1)

res = 0

for i in range(N):
    s = bit.sum(D[i])
    lt = bit.bisect_left(s)
    rt = bit.bisect_left(s + 1)
    bit.add(D[i], 1)
    res += (i + 1) * (D[i] - lt) * (rt - D[i])

print(res)

Submission status: Accepted

Solution code:
def main():
    import heapq
    N = int(input())
    a = list(map(int, input().split()))
    q = []
    LR = [[0, N-1] for i in range(N)]
    for i in range(N):
        x = a[i]
        while(q and -q[0][0] > x):
            v, id = heapq.heappop(q)
            LR[id][1] = i - 1
        heapq.heappush(q, (-x, i))

    for i in range(N-1, -1, -1):
        x = a[i]
        while(q and -q[0][0] > x):
            v, id = heapq.heappop(q)
            LR[id][0] = i+1
        heapq.heappush(q, (-x, i))
    ans = 0
    for i in range(N):
        ans += a[i] * (LR[i][1] - i + 1)*(i - LR[i][0] + 1)
    print(ans)


main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(enumerate(list(map(int, input().split()))))
A = sorted(A, key=lambda x:x[1], reverse=True)

before_idx = list(range(-1, N-1)) + [-1]
next_idx = list(range(1, N+1)) + [N]

ans = 0
for i, a in A:
  il = before_idx[i]
  ir = next_idx[i]
  ans += (i - il) * (ir - i) * a
  before_idx[ir] = il
  next_idx[il] = ir

print (ans)

Submission status: Accepted

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(n,base=2):
    rt=[]
    for tb in range(base**n):s=[tb//(base**bt)%base for bt in range(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)
 
YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
FourNb=[(1,0),(-1,0),(0,1),(0,-1)];EightNb=[(1,0),(-1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('EWNS',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()
 
class Tree:
    def __init__(self,inp_size=None,ls=None,init=True,index=0):
        self.LCA_init_stat=False
        self.ETtable=[]
        if init:
            if ls==None:
                self.stdin(inp_size,index=index)
            else:
                self.size=len(ls)+1
                self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return
 
    def stdin(self,inp_size=None,index=1):
        if inp_size==None:
            self.size=int(input())
        else:
            self.size=inp_size
        self.edges,_=GI(self.size,self.size-1,index=index)
        return
    
    def listin(self,ls,index=0):
        self.size=len(ls)+1
        self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return
 
    def __str__(self):
        return  str(self.edges)
 
    def dfs(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append(x)
        v=[-1]*self.size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==-1:
                    q.append(nb)
                    v[nb]=func(v[c],nb,d)
        return v
 
    def EulerTour(self,x):
        q=deque()
        q.append(x)
        self.depth=[None]*self.size
        self.depth[x]=0
        self.ETtable=[]
        self.ETdepth=[]
        self.ETin=[-1]*self.size
        self.ETout=[-1]*self.size
        cnt=0
        while q:
            c=q.pop()
            if c<0:
                ce=~c
            else:
                ce=c
                for nb,d in self.edges[ce]:
                    if self.depth[nb]==None:
                        q.append(~ce)
                        q.append(nb)
                        self.depth[nb]=self.depth[ce]+1
            self.ETtable.append(ce)
            self.ETdepth.append(self.depth[ce])
            if self.ETin[ce]==-1:
                self.ETin[ce]=cnt
            else:
                self.ETout[ce]=cnt
            cnt+=1
        return
    
    def LCA_init(self,root):
        self.EulerTour(root)
        self.st=SparseTable(self.ETdepth,init_func=min,init_idl=inf)
        self.LCA_init_stat=True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            self.LCA_init(root)
        xin,xout=self.ETin[x],self.ETout[x]
        yin,yout=self.ETin[y],self.ETout[y]
        a=min(xin,yin)
        b=max(xout,yout,xin,yin)
        id_of_min_dep_in_et=self.st.query_id(a,b+1)
        return self.ETtable[id_of_min_dep_in_et]
 
class SparseTable: # O(N log N) for init, O(1) for query(l,r)
    def __init__(self,ls,init_func=min,init_idl=float('inf')):
        self.func=init_func
        self.idl=init_idl
        self.size=len(ls)
        self.N0=self.size.bit_length()
        self.table=[ls[:]]
        self.index=[list(range(self.size))]
        self.lg=[0]*(self.size+1)
        
        for i in range(2,self.size+1):
            self.lg[i]=self.lg[i>>1]+1
 
        for i in range(self.N0):
            tmp=[self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) for j in range(self.size)]
            tmp_id=[self.index[i][j] if self.table[i][j]==self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) else self.index[i][min(j+(1<<i),self.size-1)] for j in range(self.size)]
            self.table+=[tmp]
            self.index+=[tmp_id]
    
    # return func of [l,r)
    def query(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        return self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))])
    
    # return index of which val[i] = func of v among [l,r)
    def query_id(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        a,b=self.index[N][l],self.index[N][max(0,r-(1<<N))]
        if self.table[0][a]==self.func(self.table[N][l],self.table[N][r-(1<<N)]):
            b=a
        return b
    
    def __str__(self):
        return str(self.table[0])
 
    def print(self):
        for i in self.table:
            print(*i)
 
class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]
 
    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo
 
show_flg=False
show_flg=True
ans=0

n=I()
a=LI()
b=[0]*n
for i in range(n):
    b[a[i]-1]=i
    
st=SparseTable(a,init_func=min,init_idl=inf)

m=n.bit_length()
for j in range(n):
    b[j]
    l=r=b[j]
    for i in range(m)[::-1]:
        if r+(1<<i)<n and st.query(b[j],r+(1<<i)+1)>=j+1:
            r+=(1<<i)
        if l-(1<<i)>=0 and st.query(l-(1<<i),b[j]+1)>=j+1:
            l-=(1<<i)
    ans+=(r-b[j]+1)*(b[j]-l+1)*(j+1)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
a_to_i = {a: i for i, a in enumerate(A, start=1)}

L = list(range(-1, N + 1))
R = list(range(1, N + 3))

ans = 0
for a in reversed(range(1, N + 1)):
    i = a_to_i[a]
    ans += a * (R[i] - i) * (i - L[i])
    L[R[i]] = L[i]
    R[L[i]] = R[i]

print(ans)

Submission status: Accepted

Solution code:
import sys
class Node:
    def __init__(self, key, height):
        self.key = key #ノードの木
        self.height = height #このノードを根とする部分木の高さ
        self.left = None
        self.right = None

    def size(self, n): return 0 if n is None else n.height

    def bias(self): #左の方が高いと正、右が高いと負の値を返す
        return self.size(self.left) - self.size(self.right)

    #木の高さの計算
    def calcSize(self):
        self.height = 1 + max(self.size(self.left), self.size(self.right))

class AVLTree:
    def __init__(self):
        self.root = None #根
        self.change = False #修正フラグ
        self.lmax = None #左部分木のキーの最大値

    ###############
    #回転操作, 修正操作
    ###############
    def rotateL(self, n): #ノードnの左回転
        r = n.right; rl = r.left
        r.left = n; n.right = rl
        r.left.calcSize()
        r.calcSize()
        return r

    def rotateR(self, n):
        l = n.left; lr = l.right
        l.right = n; n.left = lr
        l.right.calcSize()
        l.calcSize()
        return l

    def rotateLR(self, n): #二重回転;左回転→右回転
        n.left = self.rotateL(n.left)
        return self.rotateR(n)

    def rotateRL(self, n):
        n.right = self.rotateR(n.right)
        return self.rotateL(n)
        
    def balanceL(self, n):
        if not self.change: return n
        h = n.height
        if n.bias() == 2:
            if n.left.bias() >= 0: n = self.rotateR(n)
            else: n = self.rotateLR(n)
        else: n.calcSize()
        self.change = (h != n.height)
        return n

    def balanceR(self, n):
        if not self.change: return n
        h = n.height
        if n.bias() == -2:
            if n.right.bias() <= 0: n = self.rotateL(n)
            else: n = self.rotateRL(n)
        else: n.calcSize()
        self.change = (h != n.height)
        return n

    ###############
    #Nodeの追加
    ###############
    def insert(self, key): self.root = self.insert_sub(self.root, key)
    
    def insert_sub(self, t, key): #新たなノードの挿入。初期位置は根。
        if t is None:
            self.change = True
            return Node(key, 1)
        if key < t.key:
            t.left = self.insert_sub(t.left, key)
            return self.balanceL(t)
        elif key > t.key:
            t.right = self.insert_sub(t.right, key)
            return self.balanceR(t)
        else:
            self.change = False
            t.value = value
            return t

    ###############
    #Nodeの削除
    ###############
    def delete(self, key): self.root = self.delete_sub(self.root, key)

    def delete_sub(self, t, key):
        if t is None:
            self.change = False
            return None
        if key < t.key:
            t.left = self.delete_sub(t.left, key)
            return self.balanceR(t)
        elif key > t.key:
            t.right - self.delete_sub(t.right, key)
            return self.balanceL(t)
        else:
            if t.left is None:
                self.change = True
                return t.right
            else:
                t.left = self.delete_max(t.left)
                t.key = self.lmax
                t.value = self.value
                return self.balanceR(t)
    
    def delete_max(self, n):
        if n.right is None: #nの右部分木が存在しない場合は左部分木を昇格させる
            self.change = True
            self.lmax = n.key
            self.value = n.value
            return n.left
        else:
            n.right = self.delete_max(n.right)
            return self.balanceL(n)

    ###############
    #Nodeの探索
    ###############
    def search(self, key, lower, higher):
        t = self.root
        lb, hb = lower, higher
        while t:
            if key < t.key:
                hb = t.key
                t = t.left
            else:
                lb = t.key
                t = t.right
        return lb, hb
                

def solve(): #デバッグ用コード
    N = int(input())
    A = [int(a) for a in input().split()]
    Ai = dict()
    for i, a in enumerate(A): Ai[a] = i
    Tree = AVLTree()
    ini = Ai[1]
    Ans = 1 * (ini + 1) * (N - ini)
    Tree.insert(ini)
    for i in range(2, N + 1):
        ai = Ai[i]
        l, r = Tree.search(ai, -1, N)
        Ans += i * (ai - l) * (r - ai)
        Tree.insert(ai)
    print(Ans)
        
    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
class UnionFind :
    def __init__(self, size) :
        self.parent = list(range(size))
        self.height = [0] * size
        self.size = [1] * size
        self.component = size

    def root(self, index) :
        if self.parent[index] == index :  # 根の場合
            return index
        rootIndex = self.root(self.parent[index])  # 葉の場合親の根を取得
        self.parent[index] = rootIndex  # 親の付け直し
        return rootIndex

    def union(self, index1, index2) :  # 結合
        root1 = self.root(index1)
        root2 = self.root(index2)

        if root1 == root2 :  # 連結されている場合
            return

        self.component -= 1  # 連結成分を減らす

        if self.height[root1] < self.height[root2] :
            self.parent[root1] = root2  # root2に結合
            self.size[root2] += self.size[root1]
        else :
            self.parent[root2] = root1  # root1に結合
            self.size[root1] += self.size[root2]
            if self.height[root1] == self.height[root2] :
                self.height[root1] += 1
        return

    def isSameRoot(self, index1, index2) :
        return self.root(index1) == self.root(index2)

    def sizeOfSameRoot(self, index) :
        return self.size[self.root(index)]

    def getComponent(self) :
        return self.component

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

I = list(range(N))
I.sort(key=lambda i: A[i], reverse=True)

V = set()
tree = UnionFind(N)

ans = 0
for i in I:
    a = A[i]
    L = tree.sizeOfSameRoot(i - 1) if (i - 1) in V else 0
    R = tree.sizeOfSameRoot(i + 1) if (i + 1) in V else 0
    ans += a * ((L + 1) * (R + 1))

    if i - 1 in V:
        tree.union(i - 1, i)
    if i + 1 in V:
        tree.union(i + 1, i)
    V.add(i)

print(ans)