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:
n=int(input())
p=list(map(int,input().split()))
dn={x:i for i,x in enumerate(p)}

#####segfunc#####
def segfunc(x, y):
    return x+y
#################

#####ide_ele#####
ide_ele = 0
#################

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc=segfunc, ide_ele=ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

st=SegTree([0]*n)
ans=0

for k in range(1,n+1):
    i=dn[k]
    # idx=iを含み、区間和が0になる最長の区間を調べる。
    l,r=0,i
    while r-l>1:
        x=(l+r)//2
        if st.query(x,i+1)>0:
            l,r=x,r
        else:
            l,r=l,x
    l0=l if st.query(l,i+1)==0 else r
    l,r=i,n-1
    while r-l>1:
        x=(l+r)//2
        if st.query(i,x+1)>0:
            l,r=l,x
        else:
            l,r=x,r
    r0=r if st.query(i,r+1)==0 else l
    ans+=k*(i-l0+1)*(r0-i+1)
    st.update(i,1)
print(ans)

Submission status: Accepted

Solution code:
class Node:
    def __init__(self, key):
        self.key = key
        self.lch = None
        self.rch = None
        self.bias = 0


class AVLTree:
    def __init__(self):
        self.root = None

    def rotate_left(self, v):
        u = v.rch
        v.rch = u.lch
        u.lch = v
        if u.bias == -1:
            u.bias = v.bias = 0
        else:
            u.bias = 1
            v.bias = -1
        return u

    def rotate_right(self, v):
        u = v.lch
        v.lch = u.rch
        u.rch = v
        if u.bias == 1:
            u.bias = v.bias = 0
        else:
            u.bias = -1
            v.bias = 1
        return u

    def rotateLR(self, v):
        u = v.lch
        t = u.rch
        u.rch = t.lch
        t.lch = u
        v.lch = t.rch
        t.rch = v
        self.update_bias_double(t)
        return t

    def rotateRL(self, v):
        u = v.rch
        t = u.lch
        u.lch = t.rch
        t.rch = u
        v.rch = t.lch
        t.lch = v
        self.update_bias_double(t)
        return t

    def update_bias_double(self, v):
        if v.bias == 1:
            v.rch.bias = -1
            v.lch.bias = 0
        elif v.bias == -1:
            v.rch.bias = 0
            v.lch.bias = 1
        else:
            v.rch.bias = 0
            v.lch.bias = 0
        v.bias = 0

    def add(self, key):
        if self.root is None:
            self.root = Node(key)
            return

        v = self.root
        history = []
        while v is not None:
            if key < v.key:
                history.append((v, 1))
                v = v.lch
            elif v.key < key:
                history.append((v, -1))
                v = v.rch
            else:
                return

        p, pdir = history[-1]
        if pdir == 1:
            p.lch = Node(key)
        else:
            p.rch = Node(key)

        while history:
            v, direction = history.pop()
            v.bias += direction

            new_v = None
            b = v.bias
            if b == 0:
                break

            if b == 2:
                u = v.lch
                if u.bias == -1:
                    new_v = self.rotateLR(v)
                else:
                    new_v = self.rotate_right(v)
                break
            if b == -2:
                u = v.rch
                if u.bias == 1:
                    new_v = self.rotateRL(v)
                else:
                    new_v = self.rotate_left(v)
                break

        if new_v is not None:
            if len(history) == 0:
                self.root = new_v
                return
            p, pdir = history.pop()
            if pdir == 1:
                p.lch = new_v
            else:
                p.rch = new_v

    def lower_bound(self, key):
        ret = 1<<30
        v = self.root
        while v is not None:
            if v.key >= key:
                if ret > v.key:
                    ret = v.key
                v = v.lch
            else:
                v = v.rch
        return ret

    def upper_bound(self, key):
        ret = -1
        v = self.root
        while v is not None:
            if v.key <= key:
                if ret < v.key:
                    ret = v.key
                v = v.rch
            else:
                v = v.lch
        return ret

if __name__ == '__main__':
    N = int(input())
    A = [(a, i) for i, a in enumerate(map(int, input().split()))]
    A.sort(reverse=True)

    T = AVLTree()
    T.add(-1)
    T.add(N)

    ans = 0
    while A:
        a, i = A.pop()
        l = T.upper_bound(i)
        r = T.lower_bound(i)
        ans += a*(r-i)*(i-l)
        T.add(i)
    print(ans)

Submission status: Accepted

Solution code:
class Node:
    def __init__(self, key):
        self.key = key
        self.lch = None
        self.rch = None
        self.bias = 0
        self.size = 1


class AVLTree:
    def __init__(self):
        self.root = None

    def rotate_left(self, v):
        u = v.rch

        u.size = v.size
        v.size -= u.rch.size + 1 if u.rch is not None else 1

        v.rch = u.lch
        u.lch = v
        if u.bias == -1:
            u.bias = v.bias = 0
        else:
            u.bias = 1
            v.bias = -1
        return u

    def rotate_right(self, v):
        u = v.lch

        u.size = v.size
        v.size -= u.lch.size + 1 if u.lch is not None else 1

        v.lch = u.rch
        u.rch = v
        if u.bias == 1:
            u.bias = v.bias = 0
        else:
            u.bias = -1
            v.bias = 1
        return u

    def rotateLR(self, v):
        u = v.lch
        t = u.rch

        t.size = v.size
        v.size -= u.size - (t.rch.size if t.rch is not None else 0)
        u.size -= t.rch.size + 1 if t.rch is not None else 1

        u.rch = t.lch
        t.lch = u
        v.lch = t.rch
        t.rch = v
        self.update_bias_double(t)
        return t

    def rotateRL(self, v):
        u = v.rch
        t = u.lch

        t.size = v.size
        v.size -= u.size - (t.lch.size if t.lch is not None else 0)
        u.size -= t.lch.size + 1 if t.lch is not None else 1

        u.lch = t.rch
        t.rch = u
        v.rch = t.lch
        t.lch = v
        self.update_bias_double(t)
        return t

    def update_bias_double(self, v):
        if v.bias == 1:
            v.rch.bias = -1
            v.lch.bias = 0
        elif v.bias == -1:
            v.rch.bias = 0
            v.lch.bias = 1
        else:
            v.rch.bias = 0
            v.lch.bias = 0
        v.bias = 0

    def add(self, key):
        if self.root is None:
            self.root = Node(key)
            return

        v = self.root
        history = []
        while v is not None:
            if key < v.key:
                history.append((v, 1))
                v = v.lch
            elif v.key < key:
                history.append((v, -1))
                v = v.rch
            else:
                return

        p, pdir = history[-1]
        if pdir == 1:
            p.lch = Node(key)
        else:
            p.rch = Node(key)

        while history:
            v, direction = history.pop()
            v.bias += direction
            v.size += 1

            new_v = None
            b = v.bias
            if b == 0:
                break

            if b == 2:
                u = v.lch
                if u.bias == -1:
                    new_v = self.rotateLR(v)
                else:
                    new_v = self.rotate_right(v)
                break
            if b == -2:
                u = v.rch
                if u.bias == 1:
                    new_v = self.rotateRL(v)
                else:
                    new_v = self.rotate_left(v)
                break

        if new_v is not None:
            if len(history) == 0:
                self.root = new_v
                return
            p, pdir = history.pop()
            p.size += 1
            if pdir == 1:
                p.lch = new_v
            else:
                p.rch = new_v

        while history:
            p, pdir = history.pop()
            p.size += 1

    def remove(self, key):
        v = self.root
        history = []
        while v is not None:
            if key < v.key:
                history.append((v, 1))
                v = v.lch
            elif v.key < key:
                history.append((v, -1))
                v = v.rch
            else:
                break
        else:
            return False

        if v.lch is not None:
            history.append((v, 1))
            lmax = v.lch
            while lmax.rch is not None:
                history.append((lmax, -1))
                lmax = lmax.rch

            v.key = lmax.key

            v = lmax

        c = v.rch if v.lch is None else v.lch

        if history:
            p, pdir = history[-1]
            if pdir == 1:
                p.lch = c
            else:
                p.rch = c
        else:
            self.root = c
            return True

        while history:
            new_p = None

            p, pdir = history.pop()
            p.bias -= pdir
            p.size -= 1

            b = p.bias
            if b == 2:
                if p.lch.bias == -1:
                    new_p = self.rotateLR(p)
                else:
                    new_p = self.rotate_right(p)

            elif b == -2:
                if p.rch.bias == 1:
                    new_p = self.rotateRL(p)
                else:
                    new_p = self.rotate_left(p)

            elif b != 0:
                break

            if new_p is not None:
                if len(history) == 0:
                    self.root = new_p
                    return True
                gp, gpdir = history[-1]
                if gpdir == 1:
                    gp.lch = new_p
                else:
                    gp.rch = new_p
                if new_p.bias != 0:
                    break

        while history:
            p, pdir = history.pop()
            p.size -= 1

        return True

    def member(self, key):
        v = self.root
        while v is not None:
            if key < v.key:
                v = v.lch
            elif v.key < key:
                v = v.rch
            else:
                return True
        return False

    def lower_bound(self, key):
        ret = None
        v = self.root
        while v is not None:
            if v.key >= key:
                if ret is None or ret > v.key:
                    ret = v.key
                v = v.lch
            else:
                v = v.rch
        return ret

    def upper_bound(self, key):
        ret = None
        v = self.root
        while v is not None:
            if v.key <= key:
                if ret is None or ret < v.key:
                    ret = v.key
                v = v.rch
            else:
                v = v.lch
        return ret

    def find_kth_element(self, k):
        v = self.root
        s = 0
        while v is not None:
            t = s+v.lch.size if v.lch is not None else s
            if t == k:
                return v.key
            elif t < k:
                s = t+1
                v = v.rch
            else:
                v = v.lch
        return None

    def __contains__(self, key): return self.member(key)
    def __delitem__(self, key): return self.remove(key)
    def __bool__(self): return self.root is not None
    def __len__(self): return self.root.size if self.root is not None else 0


if __name__ == '__main__':
    N = int(input())
    A = [(a, i) for i, a in enumerate(map(int, input().split()))]
    A.sort(reverse=True)

    T = AVLTree()
    T.add(-1)
    T.add(N)

    ans = 0
    while A:
        a, i = A.pop()
        l = T.upper_bound(i)
        r = T.lower_bound(i)
        ans += a*(r-i)*(i-l)
        T.add(i)
    print(ans)

Submission status: Accepted

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
def main(N, A):
    ans = 0
    Ai = [(a, i + 1) for i, a in enumerate(A)]
    Ai.sort(key=lambda x: x[0])
    st = SegmentTree(n=N + 2, f=lambda x, y: x + y)
    st.set_val(0, 1)
    st.set_val(N + 1, 1)
    for a, i in Ai:
        lc = st.query(0, i)
        l = st.bisect_left(lambda x: x < lc)
        r = st.bisect_left(lambda x: x < lc + 1)
        ans += a * (i - l) * (r - i)
        st.set_val(i, 1)
    print(ans)

class SegmentTree:
    def __init__(self, n=None, f=max, identity_factory=int, initial_values=None):
        assert(n or initial_values)
        size = n if n else len(initial_values)
        d = [identity_factory() for _ in range(2 * size + 1)]
        self.__n, self.__d, self.__f, self.__e = size, d, f, identity_factory
        if initial_values:
            for i, v in enumerate(initial_values): d[size + i] = v
            for i in range(size - 1, 0, -1): d[i] = f(d[i << 1], d[i << 1 | 1])

    def get_val(self, index):
        return self.__d[index + self.__n]

    def set_val(self, index, new_value):
        i, d, f = index + self.__n, self.__d, self.__f
        if d[i] == new_value: return
        d[i], i = new_value, i >> 1
        while i:
            d[i], i = f(d[i << 1], d[i << 1 | 1]), i >> 1

    def modify(self, index, value):
        self.set_val(index, self.__f(self.__d[index + self.__n], value))

    def query(self, from_inclusive, to_exclusive):
        ans = self.__e()
        if to_exclusive <= from_inclusive: return ans
        l, r, d, f = from_inclusive + self.__n, to_exclusive + self.__n, self.__d, self.__f
        while l < r:
            if l & 1: ans, l = f(ans, d[l]), l + 1
            if r & 1: ans, r = f(d[r - 1], ans), r - 1
            l, r = l >> 1, r >> 1
        return ans

    def bisect_left(self, func):
        '''func()がFalseになるもっとも左のindexを探す
        '''
        i, j, n, f, d, v = self.__n, self.__n + self.__n, self.__n, self.__f, self.__d, self.__e()
        while i < j:
            if i & 1:
                nv = f(v, d[i])
                if not func(nv): break
                v, i = nv, i + 1
            i, j = i >> 1, j >> 1
        while i < n:
            nv = f(v, d[i << 1])
            if func(nv): v, i = nv, i << 1 | 1
            else: i = i << 1
        return i - n

if __name__ == '__main__':
    input = sys.stdin.readline
    N = int(input())
    *A, = map(int, input().split())
    main(N, A)

Submission status: Accepted

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
def main(N, A):
    ans = 0
    Ai = [(a, i + 1) for i, a in enumerate(A)]
    Ai.sort(key=lambda x: x[0])
    st = SegmentTree(n=N + 2, f=lambda x, y: x + y)
    st.set_val(0, 1)
    st.set_val(N + 1, 1)
    for a, i in Ai:
        lc = st.query(0, i)
        l = st.bisect_left(lambda x: x < lc)
        r = st.bisect_left(lambda x: x < lc + 1)
        ans += a * (i - l) * (r - i)
        st.set_val(i, 1)
    print(ans)

class SegmentTree:
    def __init__(self, n=None, f=max, identity_factory=int, initial_values=None):
        assert(n or initial_values)
        size = n if n else len(initial_values)
        d = [identity_factory() for _ in range(2 * size + 1)]
        self.__n, self.__d, self.__f, self.__e = size, d, f, identity_factory
        if initial_values:
            for i, v in enumerate(initial_values): d[size + i] = v
            for i in range(size - 1, 0, -1): d[i] = f(d[i << 1], d[i << 1 | 1])

    def get_val(self, index):
        return self.__d[index + self.__n]

    def set_val(self, index, new_value):
        i, d, f = index + self.__n, self.__d, self.__f
        if d[i] == new_value: return
        d[i] = new_value
        i = i >> 1
        while i:
            d[i] = f(d[i << 1], d[i << 1 | 1])
            i = i >> 1

    def modify(self, index, value):
        self.set_val(index, self.__f(self.__d[index + self.__n], value))

    def query(self, from_inclusive, to_exclusive):
        ans = self.__e()
        if to_exclusive <= from_inclusive: return ans
        l, r, d, f = from_inclusive + self.__n, to_exclusive + self.__n, self.__d, self.__f
        while l < r:
            if l & 1: ans, l = f(ans, d[l]), l + 1
            if r & 1: ans, r = f(d[r - 1], ans), r - 1
            l, r = l >> 1, r >> 1
        return ans

    def bisect_left(self, func):
        '''func()がFalseになるもっとも左のindexを探す
        '''
        i, n, f, d, v = 1, self.__n, self.__f, self.__d, self.__e()
        i = n
        j = n + n
        while i < j:
            if i & 1:
                nv = f(v, d[i])
                if not func(nv):
                    break
                v = nv
                i += 1
            i >>= 1
            j >>= 1
        while i < n:
            nv = f(v, d[i << 1])
            if func(nv):
                v, i = nv, i << 1 | 1
            else:
                i = i << 1
        return i - n

if __name__ == '__main__':
    input = sys.stdin.readline
    N = int(input())
    *A, = map(int, input().split())
    main(N, A)

Submission status: Accepted

Solution code:
''' 
    [Bit]
'''
class Bit:
    """ used for only int(>=0) 
        1-indexed (ignore 0-index)
    """
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
        self.depth = n.bit_length()
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

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

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

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


n = int(input())
al = list(map(int, input().split()))
bit = Bit(n)

a_to_i = [0]*(n+1)
for i,a in enumerate(al):
    a_to_i[a] = i+1

ans = 0
for a in range(1,n+1):
    curr_i = a_to_i[a]
    all_left_cnt = bit.sum(curr_i)
    if all_left_cnt == 0:
        left_cnt = curr_i
    else:
        left_i, _ = bit.lower_bound(all_left_cnt)
        left_cnt = curr_i - left_i

    right_i, _ = bit.lower_bound(all_left_cnt+1)
    right_cnt = right_i - curr_i
    all_cnt = right_cnt*left_cnt
    a_sum = a*all_cnt
    ans += a_sum
    bit.add(curr_i,1)

    # print(a,left_cnt,right_cnt)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
class BIT:
    def __init__(self,N):
        self.N=N
        self.bit=[0]*(N+1)
        self.b=1<<N.bit_length()-1
    def add(self,a,w):
        x=a
        while(x<=self.N):
            self.bit[x]+=w
            x+=x&-x
    def get(self,a):
        ret,x=0,a-1
        while(x>0):
            ret+=self.bit[x]
            x-=x&-x
        return ret
    def cum(self,l,r):
        return self.get(r)-self.get(l) 
    def lowerbound(self,w):
        if w<=0:
            return 0
        x=0
        k=self.b
        while k>0:
            if x+k<=self.N and self.bit[x+k]<w:
                w-=self.bit[x+k]
                x+=k
            k//=2
        return x+1

N=int(input())
A=list(map(int,input().split()))
dic={}
for i in range(N):
    dic[A[i]]=i+1
bit=BIT(N)
ans=0
for i in range(1,N+1):
    d=dic[i]
    bit.add(d,1)
    c=bit.get(d+1)
    L=bit.lowerbound(c-1)
    R=bit.lowerbound(c+1)
    ans+=(R-d)*(d-L)*i
print(ans)

Submission status: Accepted

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

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

B = [[A[i], i] for i in range(n)]
B.sort()

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

    rr = n-1-B[i][1]
    l = -1
    r = n+1
    m = (l+r)//2
    while r-l > 1:
        # print(R.sum(m) , i,l,r,m)
        if R.sum(m) < R.sum(rr+1):
            l = m
        else:
            r = m
        m = (l+r)//2
    # print("R", l)
    R.add(n-1-B[i][1]+1, 1)
    # print([R.sum(i+1)-R.sum(i) for i in range(n)])
    RR = l

    ans += B[i][0] * (B[i][1]-LL) * ((n-1-RR)-B[i][1])
    # print("ans", ans)
print(ans)

Submission status: Accepted

Solution code:
def make_tree(n):
    i = 2
    while True:
        if i >= n * 2:
            tree = [-1] * i
            break
        else:
            i *= 2
    return tree

def initialization(a):
    l = len(tree) // 2
    for i in range(l, l + len(a)):
        tree[i] = a[i - l]
    for i in range(l - 1, 0, -1):
        tree[i] = max(tree[2 * i], tree[2 * i + 1])
    return

def update(i, x):
    i += len(tree) // 2
    tree[i] = x
    i //= 2
    while True:
        if i == 0:
            break
        tree[i] = max(tree[2 * i], tree[2 * i + 1])
        i //= 2
    return

def find(s, t):
    s += len(tree) // 2
    t += len(tree) // 2
    ans = -1
    while True:
        if s > t:
            break
        if s % 2 == 0:
            s //= 2
        else:
            ans = max(ans, tree[s])
            s = (s + 1) // 2
        if t % 2 == 1:
            t //= 2
        else:
            ans = max(ans, tree[t])
            t = (t - 1) // 2
    return ans

n = int(input())
a = list(map(int, input().split()))
x1, x2 = [0] * n, [0] * n
tree = make_tree(n)
for i in range(n):
    update(a[i] - 1, i)
    x1[i] = find(0, a[i] - 2)
initialization([-1] * n)
for i in range(n):
    j = n - i - 1
    update(a[j] - 1, i)
    x2[j] = n - find(0, a[j] - 2) - 1
ans = 0
for i in range(n):
    ans += a[i] * (i - x1[i]) * (x2[i] - i)
print(ans)

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

dic={}
for i in range(n):
    dic[a[i]]=i+1

# Binary Indexed Tree (Fenwick Tree)
class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
    def add(self, i, x):
        # assert i > 0
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)

bi=BIT(n)
ans=0
# print(dic)
for i in range(n):
    lsum=bi.sum(dic[i+1])
    l,r=-1,dic[i+1]
    while r-l>1:
        half=(r+l)//2
        if bi.sum(half)>=lsum:
            r=half
        else:
            l=half
    ll=r
    rsum=bi.get(dic[i+1],n)
    l,r=dic[i+1],n+1
    while r-l>1:
        half=(r+l)//2
        if bi.get(half,n)>=rsum:
            l=half
        else:
            r=half
    rr=l
    ans+=(i+1)*(dic[i+1]-ll)*(rr-dic[i+1]+1)
    # print(ll,dic[i+1],rr)
    bi.add(dic[i+1],i+1)
    # print(ans)
    # print(bi.el)
print(ans)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


class BinaryIndexTree:
    def __init__(self, n):
        self.size = n
        self._container = [0] * (n + 1)
        self.depth = n.bit_length()

    def sum(self, i):
        if i == 0:
            return 0
        s = 0
        while i > 0:
            s += self._container[i]
            i -= i & (-i)
        return s

    def add(self, i, x):
        if i == 0:
            return
        while i <= self.size:
            self._container[i] += x
            i += i & (-i)

    def lower_bound(self, x):
        if x == 0:
            return 0

        s = 0
        idx = 0
        for i in range(self.depth, -1, -1):
            k = idx + (1 << i)
            if k <= self.size and s + self._container[k] < x:
                s += self._container[k]
                idx += 1 << i
        return idx + 1

    def __repr__(self):
        return str(self._container)


def main():
    n = int(readline())
    a = list(map(int, readline().split()))
    idx = dict()
    for i, x in enumerate(a, 1):
        idx[x] = i

    bt = BinaryIndexTree(n + 1)
    bt.add(n + 1, 1)
    ans = 0
    for num in range(1, n + 1):
        i = idx[num]
        s = bt.sum(i)
        left = bt.lower_bound(s)
        right = bt.lower_bound(s + 1)
        ans += num * (i - left) * (right - i)
        bt.add(i, 1)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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


n = int(input())
a = list(map(int, input().split()))
d = {}
for i,num in enumerate(a):
    d[num] = i+1
ans = 0

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

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

# a1,...,aiの和がv以上になる最小のindexを求める
def index(bit, v):
    i = 0
    k = 1
    n = len(bit)-1
    while 2*k<n:
        k *= 2
    while k>0:
        if i+k<n+1 and bit[i+k]<v:
            v -= bit[i+k]
            i += k
        k //= 2
    return i+1
bit = [0] * (n+2)
bit[n+1] = 1
for num in range(1,n+1):
    v = query(bit, d[num])
    v1 = index(bit, v) if v>0 else 0
    v2 = index(bit, v+1)
    ans += num * (d[num]-v1) * (v2 - d[num])
#     print(num, d[num], v1, v2, v, bit)
    add(bit, d[num], 1)
print(ans)

Submission status: Accepted

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

class SegmentTree:
    def __init__(self,data,op,default):
        N = len(data)
        self.N = N
        self.op = op
        self.default = default
        self.l = 2**((N-1).bit_length())
        self.data = [default]*self.l + data + [default]*(self.l-N)
        for i in range(self.l-1,0,-1):
            self.data[i] = op(self.data[2*i], self.data[2*i+1])

    def get_data(self):
        return self.data[self.l:self.l + self.N]

    def set(self,i,val):
        i += self.l
        self.data[i] = val
        i = i//2
        while i > 0:
            self.data[i] = self.op(self.data[2*i], self.data[2*i+1])
            i = i//2

    def get(self,i,j):
        i += self.l
        j += self.l
        s = self.default 
        while j-i > 0:
            if i & 1:
                s = self.op(s,self.data[i])
                i += 1
            if j & 1:
                s = self.op(s,self.data[j-1])
                j -= 1
            i = i//2
            j = j//2
        return s

AI = [(a,i) for i,a in enumerate(A)]

inf = 10**10
seg = SegmentTree(AI,min,(inf,inf))

cand = [(0,N)]

ans = 0
while cand:
    temp = []
    for l,r in cand:
        m, i = seg.get(l,r)
        ans += m * (i-l+1) * (r-i)
        if l < i:
            temp.append([l,i])
        if i+1 < r:
            temp.append([i+1,r])
    cand = temp

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(x) for x in input().split()]
index = [0]*n
for i in range(n):
    index[a[i]-1] = i+2


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):
        if i == 0:
            print("Oops! BIT is an 1-indexed tree.")
            exit()
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


ans = 0
s = BIT(n+2)
s.add(1, -1)
s.add(n+2, 1)
for i in range(n):
    s.add(index[i], 1)

    left = s.sum(index[i]) - 1
    bottom = 1
    top = index[i]
    while top - bottom > 1:
        middle = (top+bottom)//2
        if s.sum(middle) >= left:
            top = middle
        else:
            bottom = middle
    if left == -1:
        left = 1
    else:
        left = top

    right = s.sum(index[i])+1
    bottom = index[i]
    top = n+2
    while top - bottom > 1:
        middle = (top+bottom)//2
        if s.sum(middle) >= right:
            top = middle
        else:
            bottom = middle
    right = top

    ans += (i+1)*(index[i]-left)*(right-index[i])

print(ans)