Cyclic MEX (Codeforces 1905D)
Tags: Math, two pointers

For an array $$$a$$$, define its cost as $$$\sum_{i=1}^{n} \operatorname{mex} ^\dagger ([a_1,a_2,\ldots,a_i])$$$.You are given a permutation$$$^\ddagger$$$ $$$p$$$ of the set $$$\{0,1,2,\ldots,n-1\}$$$. Find the maximum cost across all cyclic shifts of $$$p$$$.$$$^\dagger\operatorname{mex}([b_1,b_2,\ldots,b_m])$$$ is the smallest non-negative integer $$$x$$$ such that $$$x$$$ does not occur among $$$b_1,b_2,\ldots,b_m$$$.$$$^\ddagger$$$A permutation of the set $$$\{0,1,2,...,n-1\}$$$ is an array consisting of $$$n$$$ distinct integers from $$$0$$$ to $$$n-1$$$ in arbitrary order. For example, $$$[1,2,0,4,3]$$$ is a permutation, but $$$[0,1,1]$$$ is not a permutation ($$$1$$$ appears twice in the array), and $$$[0,2,3]$$$ is also not a permutation ($$$n=3$$$ but there is $$$3$$$ in the array).

Input: Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases. The description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^6$$$) — the length of the permutation $$$p$$$.The second line of each test case contain $$$n$$$ distinct integers $$$p_1, p_2, \ldots, p_n$$$ ($$$0 \le p_i < n$$$) — the elements of the permutation $$$p$$$.It is guaranteed that sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output: For each test case, output a single integer — the maximum cost across all cyclic shifts of $$$p$$$.

Note: In the first test case, the cyclic shift that yields the maximum cost is $$$[2,1,0,5,4,3]$$$ with cost $$$0+0+3+3+3+6=15$$$.In the second test case, the cyclic shift that yields the maximum cost is $$$[0,2,1]$$$ with cost $$$1+1+3=5$$$.

Sample Inputs:
4
6
5 4 3 2 1 0
3
2 1 0
8
2 3 6 7 0 1 4 5
1
0

Sample Outputs:
15
5
31
1

Solution (Python):
import random
import sys, os
from io import BytesIO, IOBase
from collections import defaultdict, deque, Counter
from copy import deepcopy
from math import sqrt, ceil, log2, factorial, gcd, floor
from itertools import combinations, permutations
from functools import lru_cache, cmp_to_key
from heapq import heappop, heappush, heapreplace, heapify
from bisect import bisect_left, bisect_right
(Y, N, inf, buf_size, RANDOM) = ('YES', 'NO', float('inf'), 4096, random.randint(0, 10 ** 9))

def solve():
    n = read()
    lis = list(reads())
    ind = lis.index(0) + 1
    lis = lis[ind:] + lis[:ind]
    a = [0] * n
    a[-1] = n
    ans = res = n
    s = [(0, n)]
    for i in range(n - 1):
        cnt = 1
        while lis[i] < s[-1][0] and s:
            (x, y) = s.pop()
            cnt += y
            res -= x * y
        s.append((lis[i], cnt))
        res += lis[i] * cnt
        ans = max(ans, res)
    write(ans)

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, buf_size))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self, __size=...):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, buf_size))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')

class HashWrapper(int):

    def __init__(self, x):
        int.__init__(x)

    def __hash__(self):
        return super(HashWrapper, self).__hash__() ^ RANDOM

class SortedList:

    def __init__(self, iterable=None, _load=200):
        """"""
        if iterable is None:
            iterable = list()
        values = sorted(iterable)
        self._len = _len = len(values)
        self._load = _load
        self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
        self._list_lens = [len(_list) for _list in _lists]
        self._mins = [_list[0] for _list in _lists]
        self._fen_tree = []
        self._rebuild = True

    def _fen_build(self):
        """"""
        self._fen_tree[:] = self._list_lens
        _fen_tree = self._fen_tree
        for i in range(len(_fen_tree)):
            if i | i + 1 < len(_fen_tree):
                _fen_tree[i | i + 1] += _fen_tree[i]
        self._rebuild = False

    def _fen_update(self, index, value):
        """"""
        if not self._rebuild:
            _fen_tree = self._fen_tree
            while index < len(_fen_tree):
                _fen_tree[index] += value
                index |= index + 1

    def _fen_query(self, end):
        """"""
        if self._rebuild:
            self._fen_build()
        _fen_tree = self._fen_tree
        x = 0
        while end:
            x += _fen_tree[end - 1]
            end &= end - 1
        return x

    def _fen_findkth(self, k):
        """"""
        _list_lens = self._list_lens
        if k < _list_lens[0]:
            return (0, k)
        if k >= self._len - _list_lens[-1]:
            return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
        if self._rebuild:
            self._fen_build()
        _fen_tree = self._fen_tree
        idx = -1
        for d in reversed(range(len(_fen_tree).bit_length())):
            right_idx = idx + (1 << d)
            if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
                idx = right_idx
                k -= _fen_tree[idx]
        return (idx + 1, k)

    def _delete(self, pos, idx):
        """"""
        _lists = self._lists
        _mins = self._mins
        _list_lens = self._list_lens
        self._len -= 1
        self._fen_update(pos, -1)
        del _lists[pos][idx]
        _list_lens[pos] -= 1
        if _list_lens[pos]:
            _mins[pos] = _lists[pos][0]
        else:
            del _lists[pos]
            del _list_lens[pos]
            del _mins[pos]
            self._rebuild = True

    def _loc_left(self, value):
        """"""
        if not self._len:
            return (0, 0)
        _lists = self._lists
        _mins = self._mins
        (lo, pos) = (-1, len(_lists) - 1)
        while lo + 1 < pos:
            mi = lo + pos >> 1
            if value <= _mins[mi]:
                pos = mi
            else:
                lo = mi
        if pos and value <= _lists[pos - 1][-1]:
            pos -= 1
        _list = _lists[pos]
        (lo, idx) = (-1, len(_list))
        while lo + 1 < idx:
            mi = lo + idx >> 1
            if value <= _list[mi]:
                idx = mi
            else:
                lo = mi
        return (pos, idx)

    def _loc_right(self, value):
        """"""
        if not self._len:
            return (0, 0)
        _lists = self._lists
        _mins = self._mins
        (pos, hi) = (0, len(_lists))
        while pos + 1 < hi:
            mi = pos + hi >> 1
            if value < _mins[mi]:
                hi = mi
            else:
                pos = mi
        _list = _lists[pos]
        (lo, idx) = (-1, len(_list))
        while lo + 1 < idx:
            mi = lo + idx >> 1
            if value < _list[mi]:
                idx = mi
            else:
                lo = mi
        return (pos, idx)

    def add(self, value):
        """"""
        _load = self._load
        _lists = self._lists
        _mins = self._mins
        _list_lens = self._list_lens
        self._len += 1
        if _lists:
            (pos, idx) = self._loc_right(value)
            self._fen_update(pos, 1)
            _list = _lists[pos]
            _list.insert(idx, value)
            _list_lens[pos] += 1
            _mins[pos] = _list[0]
            if _load + _load < len(_list):
                _lists.insert(pos + 1, _list[_load:])
                _list_lens.insert(pos + 1, len(_list) - _load)
                _mins.insert(pos + 1, _list[_load])
                _list_lens[pos] = _load
                del _list[_load:]
                self._rebuild = True
        else:
            _lists.append([value])
            _mins.append(value)
            _list_lens.append(1)
            self._rebuild = True

    def discard(self, value):
        """"""
        _lists = self._lists
        if _lists:
            (pos, idx) = self._loc_right(value)
            if idx and _lists[pos][idx - 1] == value:
                self._delete(pos, idx - 1)

    def remove(self, value):
        """"""
        _len = self._len
        self.discard(value)
        if _len == self._len:
            raise ValueError('{0!r} not in list'.format(value))

    def pop(self, index=-1):
        """"""
        (pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
        value = self._lists[pos][idx]
        self._delete(pos, idx)
        return value

    def bisect_left(self, value):
        """"""
        (pos, idx) = self._loc_left(value)
        return self._fen_query(pos) + idx

    def bisect_right(self, value):
        """"""
        (pos, idx) = self._loc_right(value)
        return self._fen_query(pos) + idx

    def count(self, value):
        """"""
        return self.bisect_right(value) - self.bisect_left(value)

    def __len__(self):
        """"""
        return self._len

    def __getitem__(self, index):
        """"""
        (pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
        return self._lists[pos][idx]

    def __delitem__(self, index):
        """"""
        (pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
        self._delete(pos, idx)

    def __contains__(self, value):
        """"""
        _lists = self._lists
        if _lists:
            (pos, idx) = self._loc_left(value)
            return idx < len(_lists[pos]) and _lists[pos][idx] == value
        return False

    def __iter__(self):
        """"""
        return (value for _list in self._lists for value in _list)

    def __reversed__(self):
        """"""
        return (value for _list in reversed(self._lists) for value in reversed(_list))

    def __repr__(self):
        """"""
        return 'SortedList({0})'.format(list(self))
sys.stdin = IOWrapper(sys.stdin)
sys.stdout = IOWrapper(sys.stdout)
hx = lambda x: HashWrapper(x)
read = lambda x=int: x(sys.stdin.readline().rstrip('\r\n'))
reads = lambda x=int: map(x, read(str).split())
write = lambda *x, step=' ', end='\n': sys.stdout.write(step.join(map(str, x)) + end)
if __name__ == '__main__':
    for _ in range(read()):
        solve()

Solution (Python):
import sys
input = sys.stdin.readline

def readList():
    return list(map(int, input().split()))

def readInt():
    return int(input())

def readInts():
    return map(int, input().split())

def readStr():
    return input().strip()

def solve():
    (n, a) = (readInt(), readList())
    idx = a.index(0)
    a = a[idx:] + a[:idx]
    (ps, st) = ([-1] * n, [])
    dp = [0] * n
    dp[0] = 0
    for i in range(n - 1, -1, -1):
        v = 0
        while st and a[st[-1]] > a[i]:
            v = max(v, (st[-1] - i) * a[st[-1]] + dp[st[-1]])
            st.pop()
        dp[i] = max(dp[i], v)
        st.append(i)
    return n + max(dp)
for _ in range(int(input())):
    print(solve())

Solution (Python):
import sys
get_num = sys.stdin.readline

def read_array():
    return list(map(int, get_num().split()))

def get_int():
    return int(get_num())

def get_ints():
    return map(int, get_num().split())

def get_string():
    return get_num().strip()

def optimize(elements, start_point):
    (count, target) = (get_int(), read_array())
    swap_point = target.index(0)
    target = target[swap_point:] + target[:swap_point]
    (trackers, stack) = ([-1] * count, [])
    gains = [0] * count
    gains[0] = 0
    for i in reversed(range(count)):
        potential = 0
        while stack and target[stack[-1]] > target[i]:
            potential = max(potential, (stack[-1] - i) * target[stack[-1]] + gains[stack[-1]])
            stack.pop()
        gains[i] = max(gains[i], potential)
        stack.append(i)
    return count + max(gains)
for _ in range(get_int()):
    print(optimize(None, None))