The Number of Subpermutations (Codeforces 1175F)
Tags: Math, hashing

You have an array $$$a_1, a_2, \dots, a_n$$$. Let's call some subarray $$$a_l, a_{l + 1}, \dots , a_r$$$ of this array a subpermutation if it contains all integers from $$$1$$$ to $$$r-l+1$$$ exactly once. For example, array $$$a = [2, 2, 1, 3, 2, 3, 1]$$$ contains $$$6$$$ subarrays which are subpermutations: $$$[a_2 \dots a_3]$$$, $$$[a_2 \dots a_4]$$$, $$$[a_3 \dots a_3]$$$, $$$[a_3 \dots a_5]$$$, $$$[a_5 \dots a_7]$$$, $$$[a_7 \dots a_7]$$$.You are asked to calculate the number of subpermutations.

Input: The first line contains one integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$).The second line contains $$$n$$$ integers $$$a_1, a_2, \dots , a_n$$$ ($$$1 \le a_i \le n$$$). This array can contain the same integers.

Output: Print the number of subpermutations of the array $$$a$$$.

Note: There are $$$7$$$ subpermutations in the first test case. Their segments of indices are $$$[1, 4]$$$, $$$[3, 3]$$$, $$$[3, 6]$$$, $$$[4, 7]$$$, $$$[6, 7]$$$, $$$[7, 7]$$$ and $$$[7, 8]$$$.In the second test case $$$6$$$ subpermutations exist: $$$[1, 1]$$$, $$$[2, 2]$$$, $$$[2, 3]$$$, $$$[3, 4]$$$, $$$[4, 4]$$$ and $$$[4, 5]$$$.

Sample Inputs:
8
2 4 1 3 4 2 1 2

5
1 1 2 1 2

Sample Outputs:
7

6

Solution (Python):
import math
mod = int(1000000007)
i = lambda : map(int, input().split())
n = int(input())
a = [int(x) for x in input().split()]
t = [[0] * 21 for i in range(300005)]
for i in range(n):
    t[i][0] = a[i]

def build(n):
    for j in range(1, 20):
        for i in range(n):
            if i + (1 << j) - 1 > n - 1:
                break
            t[i][j] = max(t[i][j - 1], t[i + (1 << j - 1)][j - 1])

def query(p, q):
    (p, q) = (int(p), int(q))
    log = int(math.log2(q - p + 1))
    m = t[p][log]
    n = t[q - (1 << log) + 1][log]
    return max(m, n)
b = [-1] * (n + 2)
build(n)
max1 = -1
ans = 0
for i in range(n):
    max1 = max(max1, b[a[i]])
    b[a[i]] = i
    x = b[1]
    while x > max1:
        if x <= max1:
            break
        p = query(x, i)
        if p == i - x + 1:
            ans += 1
            x = b[p + 1]
        else:
            x = i - p + 1
print(ans)

Solution (Python):
import sys
import math
input = sys.stdin.readline
mod = int(1000000007)
i = lambda : map(int, input().split())
n = int(input())
a = [int(x) for x in input().split()]
t = [[0] * 21 for i in range(300005)]
for i in range(n):
    t[i][0] = a[i]

def build(n):
    for j in range(1, 20):
        for i in range(n):
            if i + (1 << j) - 1 > n - 1:
                break
            t[i][j] = max(t[i][j - 1], t[i + (1 << j - 1)][j - 1])

def query(p, q):
    (p, q) = (int(p), int(q))
    log = int(math.log2(q - p + 1))
    m = t[p][log]
    n = t[q - (1 << log) + 1][log]
    return max(m, n)
b = [-1] * (n + 2)
build(n)
max1 = -1
ans = 0
for i in range(n):
    max1 = max(max1, b[a[i]])
    b[a[i]] = i
    x = b[1]
    while x > max1:
        if x <= max1:
            break
        p = query(x, i)
        if p == i - x + 1:
            ans += 1
            x = b[p + 1]
        else:
            x = i - p + 1
print(ans)

Solution (Python):
import random, sys, os, math, gc
from collections import Counter, defaultdict, deque
from functools import lru_cache, reduce, cmp_to_key
from itertools import accumulate, combinations, permutations, product
from heapq import nsmallest, nlargest, heapify, heappop, heappush
from io import BytesIO, IOBase
from copy import deepcopy
from bisect import bisect_left, bisect_right
from math import factorial, gcd
from operator import mul, xor
from types import GeneratorType
BUFSIZE = 8192
MOD = 10 ** 9 + 7
MODD = 998244353
INF = float('inf')
D4 = [(1, 0), (0, 1), (-1, 0), (0, -1)]
D8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

def solve():
    n = II()
    arr = LII()
    h = [random.randint(0, (1 << 64) - 1) for _ in range(n + 1)]
    h[0] = 0
    num = list(accumulate(h, xor))
    ans = arr.count(1)

    def calc():
        nonlocal ans
        cum = [h[i] for i in arr]
        cum = list(accumulate(cum, xor)) + [0]
        for i in range(n):
            if arr[i] != 1:
                continue
            mx = 1
            for j in range(i + 1, n):
                if arr[j] == 1:
                    break
                mx = max(mx, arr[j])
                if j + 1 >= mx and j - i + 1 <= mx and (num[mx] == cum[j] ^ cum[j - mx]):
                    ans += 1
    calc()
    arr = arr[::-1]
    calc()
    print(ans)

def main():
    t = 1
    for _ in range(t):
        solve()

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc

def bitcnt(n):
    c = (n & 6148914691236517205) + (n >> 1 & 6148914691236517205)
    c = (c & 3689348814741910323) + (c >> 2 & 3689348814741910323)
    c = (c & 1085102592571150095) + (c >> 4 & 1085102592571150095)
    c = (c & 71777214294589695) + (c >> 8 & 71777214294589695)
    c = (c & 281470681808895) + (c >> 16 & 281470681808895)
    c = (c & 4294967295) + (c >> 32 & 4294967295)
    return c

def lcm(x, y):
    return x * y // gcd(x, y)

def lowbit(x):
    return x & -x

def perm(n, r):
    return factorial(n) // factorial(n - r) if n >= r else 0

def comb(n, r):
    return factorial(n) // (factorial(r) * factorial(n - r)) if n >= r else 0

def probabilityMod(x, y, mod):
    return x * pow(y, mod - 2, mod) % mod

class SortedList:

    def __init__(self, iterable=[], _load=200):
        """"""
        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))

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, BUFSIZE))
            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):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            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')
sys.stdin = IOWrapper(sys.stdin)
input = lambda : sys.stdin.readline().rstrip('\r\n')

def I():
    return input()

def II():
    return int(input())

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

def LI():
    return list(input().split())

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

def GMI():
    return map(lambda x: int(x) - 1, input().split())

def LGMI():
    return list(map(lambda x: int(x) - 1, input().split()))

def getGraph(n, m, directed=False):
    d = [[] for _ in range(n)]
    for _ in range(m):
        (u, v) = LGMI()
        d[u].append(v)
        if not directed:
            d[v].append(u)
    return d

def getWeightedGraph(n, m, directed=False):
    d = [[] for _ in range(n)]
    for _ in range(m):
        (u, v, w) = LII()
        u -= 1
        v -= 1
        d[u].append((v, w))
        if not directed:
            d[v].append((u, w))
    return d
if __name__ == '__main__':
    main()