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

n, *aaa = map(int, sys.stdin.buffer.read().split())
aaa_with_index = list(enumerate(aaa, start=1))
aaa_with_index.sort(key=itemgetter(1), reverse=True)
left = list(range(-1, n + 1))
right = list(range(1, n + 3))
ans = 0
for i, a in aaa_with_index:
    li = left[i]
    ri = right[i]
    ans += a * (i - li) * (ri - i)
    left[ri] = li
    right[li] = ri

print(ans)

Submission status: Accepted

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

n, *a = map(int, read().split())
ans = 0
l = list(range(n + 1))
r = list(range(n + 1))
memo = [0] * (n + 1)
for i, aa in enumerate(a):
    memo[aa] = i
for i in range(n, -1, -1):
    v = memo[i]
    ans += (v - l[v] + 1) * (r[v] - v + 1) * i
    l[r[v] + 1], r[l[v] - 1] = l[v], r[v]
print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc140/submissions/7411285

def main():
    N = int(input())
    *a, = map(int, input().split())

    xtoi = [-1] * (N + 1)
    for i, x in enumerate(a):
        xtoi[x] = i

    L = [-1] * (N + 2)
    R = [N] * (N + 2)
    for i in range(N):
        L[i] = i - 1
        R[i] = i + 1

    ans = 0
    for x, ind in zip(range(N, 0, -1), reversed(xtoi)):
        # l1, ..., x, ..., r1
        # (ll,r1)
        l1 = L[ind]
        r1 = R[ind]
        ans += x * (ind - l1) * (r1 - ind)
        L[r1] = l1
        R[l1] = r1
    print(ans)


if __name__ == '__main__':
    main()

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 = [i - 1 for i in range(N + 2)]
R = [i + 1 for i in range(N + 2)]

ans = 0
for a in range(N, 0, -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

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


class UnionFind:
    def __init__(self, n: int):
        self.n = n
        self.parents = [-1] * n
    
    def find(self, x: int):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x: int, y: int):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return
        if self.parents[y] < self.parents[x]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x: int):
        return -self.parents[self.find(x)]
    
    def same(self, x: int, y: int):
        return self.find(x) == self.find(y)
    
    def members(self, x: int):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    
    def group_count(self):
        return len(self.roots())
    
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def solve():
    N = int(rl())
    a = list(map(int, rl().split()))
    
    b = [0] * (N + 1)
    for i, x in enumerate(a):
        b[x] = i
    
    uf = UnionFind(N)
    ans = 0
    for idx in b[:0:-1]:
        left, right = 1, 1
        if 0 <= idx - 1 and a[idx] < a[idx - 1]:
            left += uf.size(idx - 1)
            uf.union(idx - 1, idx)
        if idx + 1 <= N - 1 and a[idx] < a[idx + 1]:
            right += uf.size(idx + 1)
            uf.union(idx, idx + 1)
        ans += left * right * a[idx]
    print(ans)


if __name__ == '__main__':
    solve()

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 same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

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

plc = [0 for i in range(n)]
for i in range(n):
  plc[a[i]-1] = i
ans = 0
uf = UnionFind(n)
for i in range(n)[::-1]:
  p = plc[i]
  x = i+1
  if p < n-1 and a[p] < a[p+1]:
    x *= uf.size(p+1)+1
    uf.union(p,p+1)
  if p > 0 and a[p-1] > a[p]:
    x *= uf.size(p-1)+1
    uf.union(p-1,p)
  ans += x
print(ans)

Submission status: Accepted

Solution code:
from bisect import*
class SquareSkipList:
    def __init__(self,values=[],square=1000,seed=42):
        INF=10**18
        self.square=square
        self.layer1=layer1=[]
        self.layer0=layer0=[]
        y=seed
        l0=[]
        for v in values:
            y^=(y&0x7ffff)<<13
            y^=y>>17
            y^=(y&0x7ffffff)<<5
            if y%square<1:
                layer0+=l0,
                l0=[]
                layer1+=v,
            else:l0+=v,
        layer1+=INF,
        layer0+=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):
        layer1,layer0=self.layer1,self.layer0
        idx1=bisect_left(layer1,x)
        layer0_idx1=layer0[idx1]
        idx0=bisect_left(layer0_idx1,x)
        if idx0==len(layer0_idx1):
            del layer1[idx1]
            layer0[idx1]+=layer0.pop(idx1+1)
        else:del layer0_idx1[idx0]
    def search_higher(self,x):
        layer1,layer0=self.layer1,self.layer0
        idx1=bisect(layer1,x)
        layer0_idx1=layer0[idx1]
        idx0=bisect(layer0_idx1,x)
        return layer1[idx1]if idx0==len(layer0_idx1)else layer0_idx1[idx0]
    def search_lower(self,x):
        layer1,layer0=self.layer1,self.layer0
        idx1=bisect_left(layer1,x)
        layer0_idx1=layer0[idx1]
        idx0=bisect_left(layer0_idx1,x)
        return layer1[idx1-1]if idx0<1else layer0_idx1[idx0-1]
    def pop(self,idx):
        layer1,layer0=self.layer1,self.layer0
        s=-1
        for i,l0 in enumerate(layer0):
            s+=len(l0)+1
            if s>=idx:break
        if s==idx:
            layer0[i]+=layer0[i+1]
            del layer0[i+1]
            return layer1.pop(i)
        else:return layer0[i].pop(idx-s)
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:
import sys
sys.setrecursionlimit(10 ** 7)

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

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

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


class SegmentTree:
    """
    引数：
        N: 処理する区間の長さ
        operator: モノイド演算 (max, min, __add__,ラムダ式,関数定義など)
        UNIT: 単位元
        a: 長さNの配列 a で初期化（a を与えない場合、単位元で初期化）
    注意: 内部的には 1-indexed
    """

    def __init__(self, N, operator, unit, a=None):
        self.op = operator
        self.UNIT = unit

        self.N0 = 2**(N-1).bit_length()
        self.tree = [self.UNIT]*(2*self.N0)
        if a != None:
            self.tree[self.N0:self.N0+N] = a[:]
            for k in range(self.N0-1, 0, -1):
                self.tree[k] = self.op(self.tree[2*k], self.tree[2*k+1])

    # a_k の値を x に更新
    def update(self, k, x):
        k += self.N0
        self.tree[k] = x
        k //= 2
        while k:
            self.tree[k] = self.op(self.tree[2*k], self.tree[2*k+1])
            k //= 2

    # 区間[l,r)をopでまとめる
    def query(self, l, r):
        L = l + self.N0
        R = r + self.N0
        s = self.UNIT
        while L < R:
            if R & 1:
                R -= 1
                s = self.op(self.tree[R], s)
            if L & 1:
                s = self.op(s, self.tree[L])
                L += 1
            L >>= 1
            R >>= 1
        return s

    def get(self, k):  # k番目の値を取得。query[k,k]と同じ
        return self.tree[k + self.N0]

    def all(self):
        return self.tree[1]


seg_sml = SegmentTree(N, min, N)
seg_big = SegmentTree(N, max, -1)

ans = 0

for a in range(1, N + 1):
    i = idx[a]
    l = seg_big.query(0, i)
    r = seg_sml.query(i, N)

    left = i - l - 1
    right = r - i - 1

    cnt = (r - l - 1) * (r - l) // 2
    cnt -= left * (left + 1) // 2
    cnt -= right * (right + 1) // 2

    ans += cnt * a

    seg_sml.update(i, i)
    seg_big.update(i, i)


print(ans)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    a = list(map(int, input().split()))
    l = [-1] * N
    s = []
    for i, v in enumerate(a):
        while s and  s[-1][0] > v:
            s.pop()
        if s:
            l[i] = s[-1][1]
        s.append((v, i))
    r = [N] * N
    s = []
    for i, v in (enumerate(reversed(a))):
        while s and s[-1][0] > v:
            s.pop()
        if s:
            r[N - i - 1] = s[-1][1]
        s.append((v, N - i - 1))
    ans = 0
    for i in range(N):
        rr = r[i] - 1
        ll = l[i] + 1
        ans += ((rr - i + 1) * (i - ll) + rr - i)*a[i] + a[i]
    return ans
print(main())

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    L, R = [0] * N, [0] * N
    s = [(-1, -1)]
    for i, a in enumerate(A):
        while s[-1][0] >= a:
            s.pop()
        L[i] = i - s[-1][1]
        s.append((a, i))
    s = [(-1, N)]
    for i in reversed(range(N)):
        a = A[i]
        while s[-1][0] >= a:
            s.pop()
        R[i] = s[-1][1] - i
        s.append((a, i))
    return sum(a * l * r for a, l, r in zip(A, L, R))

print(main())

Submission status: Accepted

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = lr()

def min_range(A):
    smaller = [[0, -1]]
    ret = []
    for i, a in enumerate(A):
        while smaller[-1][0] > a:
            smaller.pop()
        ret.append(i-smaller[-1][1])
        smaller.append([a, i])
    return ret

B = min_range(A)
C = min_range(A[::-1])[::-1]

answer = 0
for i in range(N):
    answer += A[i] * B[i] * C[i]

print(answer)

Submission status: Accepted

Solution code:
def examA():
    X = SI()
    d = defaultdict(int)
    for s in X:
        if s=="T" and d["S"]>=1:
            d["S"] -=1
        else:
            d[s] += 1
    ans = d["S"] + d["T"]
    print(ans)
    return

def examB():
    # 参考 earlgrey_yh
    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  # 修正フラグ

        ###############
        # 回転操作, 修正操作
        ###############
        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
                return t

        ###############
        # 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
    N = I()
    A = LI()
    lst = [0] * N
    for i in range(N):
        lst[A[i]-1] = i
    AVL = AVLTree()
    ans = 0
    for a in range(1,N+1):
        i = lst[a-1]
        l, r = AVL.search(i,-1,N)
        AVL.insert(i)
        #print(l,r)
        ans += (i-l)*(r-i)*a
        #print(l,r,i,ans)
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examB()

"""

"""

Submission status: Accepted

Solution code:
#import decimal
#decimal.getcontext().prec==500 Floatの桁数を500まで増やす
#Decimal(c).sqrt() それで平方根を求める
#Decimal(1) / Decimal(7) 1/7
"""
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd
import sys"""
#input = sys.stdin.readline


#N=int(input())

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

lst=[[A[0],0,1]]
count=0

for i in range(1,N):
    m=1
    while lst and lst[-1][0]>A[i]:
        a,b,c=lst.pop()
        count+=a*(i-b)*c
        m+=c
    lst.append([A[i],i,m])
while lst:
    a,b,c=lst.pop()
    count+=a*(N-b)*c

print(count)

Submission status: Accepted

Solution code:
#import decimal
#decimal.getcontext().prec==500 Floatの桁数を500まで増やす
#Decimal(c).sqrt() それで平方根を求める
#Decimal(1) / Decimal(7) 1/7
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd
import sys
#input = sys.stdin.readline


#N=int(input())

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

lst=[[A[0],0,1]]
count=0

for i in range(1,N):
    m=1
    while lst and lst[-1][0]>A[i]:
        a,b,c=lst.pop()
        count+=a*(i-b)*c
        m+=c
    lst.append([A[i],i,m])
while lst:
    a,b,c=lst.pop()
    count+=a*(N-b)*c

print(count)

Submission status: Accepted

Solution code:
import bisect
from collections import defaultdict
class SqrtSet:
    def __init__(self, block_limit=201):
        self.key = []
        self.child = [[]]
        self.block_limit = block_limit
 
    def search_lower(self, key):
        if key is None:
            return None
        ret = None
        i = bisect.bisect_left(self.key, key)
        if i != 0:
            ret = self.key[i - 1]
        block = self.child[i]
        i = bisect.bisect_left(block, key)
        if i != 0:
            ret = block[i - 1]
        return ret
        
    def search_higher(self, key):
        if key is None:
            return None
        ret = None
        i = bisect.bisect_right(self.key, key)
        if i != len(self.key):
            ret = self.key[i]
        block = self.child[i]
        i = bisect.bisect_right(block, key)
        if i != len(block):
            ret = block[i]
        return ret
 
    def insert(self, key):
        i = bisect.bisect(self.key, key)
        block = self.child[i]
        bisect.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 = int(input())
    A = [int(i) for i in input().split()]

    # IDX[n] <-> A.index(n)
    IDX = defaultdict(int)
    for idx,a in enumerate(A):
        IDX[a] = idx

    SS = SqrtSet()
    SS.insert(-1)
    SS.insert(N)

    ans = 0
    for n in range(1, N + 1):
        H = SS.search_higher(IDX[n])
        L = SS.search_lower(IDX[n])
        ans += (IDX[n] - L) * (H - IDX[n]) *  n
        SS.insert(IDX[n])

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.p = [e for e in range(n)]
        self.rank = [0] * n
        self.size = [1] * n

    def same(self, u, v):
        return self.find_set(u) == self.find_set(v)

    def unite(self, u, v):
        u = self.find_set(u)
        v = self.find_set(v)

        if u == v:
            return

        if self.rank[u] > self.rank[v]:
            self.p[v] = u
            self.size[u] += self.size[v]
        else:
            self.p[u] = v
            self.size[v] += self.size[u]
            if self.rank[u] == self.rank[v]:
                self.rank[v] += 1

    def find_set(self, u):
        if u != self.p[u]:
            self.p[u] = self.find_set(self.p[u])

        return self.p[u]

    def update_p(self):
        for u in range(self.n):
            self.find_set(u)

    def get_size(self, u):
        return self.size[self.find_set(u)]


n = int(input())
a = [0] + list(map(int, input().split())) + [n + 1]

idx = [0] * (n + 2)
for i, e in enumerate(a):
    idx[e] = i

uf_l = UnionFind(n + 2)
uf_r = UnionFind(n + 2)

ans = 0
for num in range(n, 0, -1):
    i = idx[num]
    ans += num * (uf_l.get_size(i) * uf_r.get_size(i))
    uf_l.unite(i, i + 1)
    uf_r.unite(i, i - 1)

print(ans)

Submission status: Accepted

Solution code:
import sys
from bisect import bisect

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 #修正フラグ

    ###############
    #回転操作, 修正操作
    ###############
    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
            return t

    ###############
    #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():
    input = sys.stdin.readline
    N = int(input())
    P = [int(p) for p in input().split()]
    pindex = dict() 
    for i, p in enumerate(P): pindex[p - 1] = i

    Ans = (pindex[0] + 1) * (N - pindex[0])
    T = AVLTree()
    T.insert(pindex[0])
    for i in range(1, N):
        pid = pindex[i]
        l, r = T.search(pid, -1, N)
        Ans += (i + 1) * (pid - l) * (r - pid)
        T.insert(pid)      

    print(Ans)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import bisect


class SqrtSet:
    def __init__(self, block_limit=201):
        self.key = []
        self.child = [[]]
        self.block_limit = block_limit

    def search_lower(self, key):
        if key is None:
            return None
        ret = None
        i = bisect.bisect_left(self.key, key)
        if i != 0:
            ret = self.key[i - 1]
        block = self.child[i]
        i = bisect.bisect_left(block, key)
        if i != 0:
            ret = block[i - 1]
        return ret
        
    def search_higher(self, key):
        if key is None:
            return None
        ret = None
        i = bisect.bisect_right(self.key, key)
        if i != len(self.key):
            ret = self.key[i]
        block = self.child[i]
        i = bisect.bisect_right(block, key)
        if i != len(block):
            ret = block[i]
        return ret

    def insert(self, key):
        i = bisect.bisect(self.key, key)
        block = self.child[i]
        bisect.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 dump(self):
        for b in self.child:
            print(len(b), end=" ")
        print("")
            
            
def main():
    n = int(input())
    p = list(map(int, input().split()))
    idx = [0] * n
    for i in range(0, n):
        idx[i] = i
    idx.sort(key=lambda i: p[i])
    t = SqrtSet()
    t.insert(-1)
    t.insert(n)
    ans = 0
    for i in range(n):
        right = t.search_higher(idx[i])
        left = t.search_lower(idx[i])
        ans+=(i+1)*(idx[i]-left)*(right-idx[i])
        t.insert(idx[i])
        #print(left,idx[i],right)
    print(ans)


main()

Submission status: Accepted

Solution code:
import random
import time
# Treap

# d = 0: right rotation
# d = 1: left rotation
def rotate(nd, d):
    c = nd[d]
    if d:
        e = c[1]
        nd[1] = c[0]
        c[0] = nd
    else:
        e = c[0]
        nd[0] = c[1]
        c[1] = nd

    r = c[4] = nd[4]
    nd[4] = r - (e[4] if e else 0) - 1
    return c

# insert a node with key = val and priority = pri
root = None
def insert(val, pri):
    global root
    st = []
    dr = []
    x = root
    while x:
        st.append(x)
        if x[2] == val:
            return
        d = (x[2] < val)
        dr.append(d)
        x = x[d]

    # [<left>, <right>, <key>, <priority>, <count>]
    nd = [None, None, val, pri, 1]
    while st:
        x = st.pop(); d = dr.pop()
        x[d] = nd
        x[4] += 1
        if x[3] >= nd[3]:
            break
        rotate(x, d)
    else:
        root = nd

    for x in st:
        x[4] += 1

def __delete(nd):
    st = []; dr = []
    while nd[0] or nd[1]:
        l = nd[0]; r = nd[1]
        d = (l[3] <= r[3]) if l and r else (l is None)
        st.append(rotate(nd, d))
        dr.append(d ^ 1)
    nd = x = None
    while st:
        nd = x; x = st.pop(); d = dr.pop()
        x[d] = nd
        x[4] -= 1
    return x

def delete(val):
    global root
    x = root

    st = []
    y = None
    while x:
        if val == x[2]:
            break
        y = x; d = (x[2] < val)
        st.append(y)
        x = x[d]
    else:
        return

    if y:
        y[d] = __delete(x)
        for x in st:
            x[4] -= 1
    else:
        root = __delete(x)

def find(val):
    global root
    x = root
    while x:
        if val == x[2]:
            return 1
        x = x[x[2] < val]
    return 0

def search1(val):
    global root
    x = root
    ans=-1
    while x:
        if val==x[2]:
            return val
        if val>x[2]:
            ans=max(ans,x[2])
            if x[1]==None:
                return ans
            else:
                x=x[1]
        if val<x[2]:
            if x[0]==None:
                return ans
            else:
                x=x[0]
    return ans

def search2(val):
    global root
    x=root
    ans=10**20
    while x:
        if val==x[2]:
            return val
        if val>x[2]:
            if x[1]==None:
                return ans
            else:
                x=x[1]
        if val<x[2]:
            ans=min(ans,x[2])
            if x[0]==None:
                return ans
            else:
                x=x[0]
    return ans



N=int(input())
A=list(map(int,input().split()))
A=[A[i]-1 for i in range(0,N)]
function=[0 for i in range(0,N)]
for i in range(0,N):
    function[A[i]]=i

random.seed()
randint=random.randint

insert(function[0],randint(1,200000))
data1=[0 for i in range(0,N)]
data2=[0 for i in range(0,N)]
data1[0]=-1
data2[0]=N
for i in range(1,N):
    if search1(function[i])!=-1:
        data1[i]=search1(function[i])
    else:
        data1[i]=-1
    if search2(function[i])!=10**20:
        data2[i]=search2(function[i])
    else:
        data2[i]=N
    insert(function[i],randint(1,200000))

ans=0
for i in range(0,N):
    prod=(function[i]-data1[i])*(data2[i]-function[i])
    ans+=prod*(i+1)

print(ans)

Submission status: Accepted

Solution code:

# 1-indexed　Binary Indexed Tree
class BIT:
    def __init__(self, n, init_list):
        self.num = n+1
        self.tree = [0]*self.num
        for i,e in enumerate(init_list):
            self.update(i,e)

    def update(self,k,x):
        k = k+1
        while k < self.num:
            self.tree[k] += x
            k += (k&(-k))
        return 
    
    # sum([l,r))
    def query(self, l,r):
        ret = 0
        while r>0:
            ret += self.tree[r]
            r -= r&(-r)
        while l>0:
            ret -= self.tree[l]
            l -= l&(-l)
        
        return ret


N = int(input())
A = list(map(int,input().split()))
#%%
idxlist = [0]*N
for i,a in enumerate(A):
    idxlist[a-1] = i


ans = 0
seg = BIT(N,[0]*N)

def judge(l,r):
    if l>r:
        l,r = r,l
    res = seg.query(l,r+1)
    if res:
        return False
    else:
        return True


for idx in idxlist:    
    ng_l = -1
    ng_r = N
    left = idx
    while abs(left-ng_l)>1:
        mid = (left+ng_l)//2
        if judge(idx,mid):
            left = mid
        else:
            ng_l = mid
    
    right = idx
    while abs(ng_r-right)>1:
        mid = (right+ng_r)//2
        if judge(idx,mid):
            right = mid
        else:
            ng_r = mid
    
    ans += A[idx]*(idx-left+1)*(right-idx+1)
    seg.update(idx,1)
    
print(ans)