Yet Another Array Counting Problem (Codeforces 1748E)
Tags: Math, flows

The position of the leftmost maximum on the segment $$$[l; r]$$$ of array $$$x = [x_1, x_2, \ldots, x_n]$$$ is the smallest integer $$$i$$$ such that $$$l \le i \le r$$$ and $$$x_i = \max(x_l, x_{l+1}, \ldots, x_r)$$$.You are given an array $$$a = [a_1, a_2, \ldots, a_n]$$$ of length $$$n$$$. Find the number of integer arrays $$$b = [b_1, b_2, \ldots, b_n]$$$ of length $$$n$$$ that satisfy the following conditions:   $$$1 \le b_i \le m$$$ for all $$$1 \le i \le n$$$;  for all pairs of integers $$$1 \le l \le r \le n$$$, the position of the leftmost maximum on the segment $$$[l; r]$$$ of the array $$$b$$$ is equal to the position of the leftmost maximum on the segment $$$[l; r]$$$ of the array $$$a$$$. Since the answer might be very large, print its remainder modulo $$$10^9+7$$$.

Input: Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^3$$$) — the number of test cases.The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n,m \le 2 \cdot 10^5$$$, $$$n \cdot m \le 10^6$$$).The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le m$$$) — the array $$$a$$$.It is guaranteed that the sum of $$$n \cdot m$$$ over all test cases doesn't exceed $$$10^6$$$.

Output: For each test case print one integer — the number of arrays $$$b$$$ that satisfy the conditions from the statement, modulo $$$10^9+7$$$.

Note: In the first test case, the following $$$8$$$ arrays satisfy the conditions from the statement:   $$$[1,2,1]$$$;  $$$[1,2,2]$$$;  $$$[1,3,1]$$$;  $$$[1,3,2]$$$;  $$$[1,3,3]$$$;  $$$[2,3,1]$$$;  $$$[2,3,2]$$$;  $$$[2,3,3]$$$. In the second test case, the following $$$5$$$ arrays satisfy the conditions from the statement:   $$$[1,1,1,1]$$$;  $$$[2,1,1,1]$$$;  $$$[2,2,1,1]$$$;  $$$[2,2,2,1]$$$;  $$$[2,2,2,2]$$$. 

Sample Inputs:
4
3 3
1 3 2
4 2
2 2 2 2
6 9
6 9 6 9 6 9
9 100
10 40 20 20 100 60 80 60 60

Sample Outputs:
8
5
11880
351025663

Solution (Python):
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
from collections import deque
M = 10 ** 9 + 7

class segment_tree(object):

    def merge(self, num, curr):
        if self.flag:
            return min(curr, num)
        else:
            return max(curr, num)

    def __init__(self, n, initial, flag):
        self.flag = flag
        self.n = n
        self.arr = [0] * (2 * n)
        for i in range(2 * n - 1, 0, -1):
            if i >= n:
                self.arr[i] = initial[i - n]
            else:
                self.arr[i] = self.merge(self.arr[2 * i], self.arr[2 * i + 1])

    def update(self, index, target):
        self.arr[index] = target
        if index & 1:
            nexttarget = self.merge(self.arr[index], self.arr[index - 1])
        else:
            nexttarget = self.merge(self.arr[index], self.arr[index + 1])
        if index > 0:
            self.update(index >> 1, nexttarget)

    def addnum(self, index, diff):
        self.update(index + self.n, self.arr[index + self.n] + diff)

    def query(self, left, right):
        (i, j) = (self.n + left, self.n + right + 1)
        if self.flag:
            output = float('inf')
        else:
            output = -float('inf')
        while i < j:
            if i & 1:
                output = self.merge(self.arr[i], output)
                i += 1
            if j & 1:
                j -= 1
                output = self.merge(self.arr[j], output)
            i = i >> 1
            j = j >> 1
        return output

def getranking(arr):
    temp = []
    n = len(arr)
    output = [0] * n
    for i in range(len(arr)):
        temp.append((arr[i], i))
    temp.sort(key=lambda x: (-x[0], x[1]))
    for i in range(n):
        output[temp[i][1]] = i
    return output

def main(t):
    (n, m) = map(int, input().split())
    arr = list(map(int, input().split()))
    ranking = getranking(arr)
    seg = segment_tree(n, ranking, True)
    dic = {}
    for i in range(n):
        dic[ranking[i]] = i
    leftnode = [-1] * n
    rightnode = [-1] * n
    queue = deque()
    root = dic[0]
    queue.append((0, n - 1, root))
    seq = []
    while queue:
        (left, right, index) = queue.popleft()
        seq.append(index)
        if left <= index - 1:
            leftnode[index] = dic[seg.query(left, index - 1)]
            queue.append((left, index - 1, leftnode[index]))
        if index + 1 <= right:
            rightnode[index] = dic[seg.query(index + 1, right)]
            queue.append((index + 1, right, rightnode[index]))
    seq = seq[::-1]
    dp = [[0 for _ in range(m + 1)] for _ in range(n)]
    accudp = [[0 for _ in range(m + 1)] for _ in range(n)]
    for index in seq:
        if leftnode[index] < 0 and rightnode[index] < 0:
            for i in range(1, m + 1):
                accudp[index][i] = i
            continue
        for i in range(1, m + 1):
            dp[index][i] = 1
            if leftnode[index] >= 0:
                dp[index][i] = accudp[leftnode[index]][i - 1]
            if rightnode[index] >= 0:
                dp[index][i] *= accudp[rightnode[index]][i]
                dp[index][i] %= M
            accudp[index][i] = accudp[index][i - 1] + dp[index][i]
            accudp[index][i] %= M
    print(accudp[root][m])
T = int(input())
t = 1
while t <= T:
    main(t)
    t += 1

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

class SegmentTree:

    def __init__(self, data, default=(-1, 0), func=max):
        """"""
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()
        self.data = [default] * (2 * _size)
        self.data[_size:_size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])

    def __delitem__(self, idx):
        self[idx] = self._default

    def __getitem__(self, idx):
        return self.data[idx + self._size]

    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1

    def __len__(self):
        return self._len

    def query(self, start, stop):
        """"""
        start += self._size
        stop += self._size
        res_left = res_right = self._default
        while start < stop:
            if start & 1:
                res_left = self._func(res_left, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res_right = self._func(self.data[stop], res_right)
            start >>= 1
            stop >>= 1
        return self._func(res_left, res_right)

    def __repr__(self):
        return 'SegmentTree({0})'.format(self.data)

def process(A, m):
    n = len(A)
    d = [(A[i], -1 * i) for i in range(n)]
    S = SegmentTree(data=d)
    children = [[None, None] for i in range(3 * n + 1)]
    parent = [None for i in range(3 * n + 1)]
    parent[0] = -1
    I = 0
    start = [[(0, n - 1, None, None)]]
    while True:
        next_s = []
        for (l, r, I2, state) in start[-1]:
            (ai, i2) = S.query(l, r + 1)
            i2 = -1 * i2
            if I > 0:
                parent[I] = I2
            if state == 'left':
                children[I2][0] = I
            elif state == 'right':
                children[I2][1] = I
            if l != i2:
                next_s.append((l, i2 - 1, I, 'left'))
            if r != i2:
                next_s.append((i2 + 1, r, I, 'right'))
            I += 1
        if len(next_s) == 0:
            break
        start.append(next_s)
    info = [None for i in range(I + 1)]
    for J in range(3 * n, -1, -1):
        if parent[J] is not None:
            info[J] = [0 for i in range(m + 1)]
            if children[J] == [None, None]:
                for i in range(1, m + 1):
                    info[J][i] = i
            elif children[J][1] == None:
                (a, b) = children[J]
                for i in range(1, m + 1):
                    info[J][i] = info[J][i - 1] + info[a][i - 1]
            elif children[J][0] == None:
                (a, b) = children[J]
                for i in range(1, m + 1):
                    info[J][i] = info[J][i - 1] + info[b][i]
            else:
                (a, b) = children[J]
                for i in range(1, m + 1):
                    info[J][i] = info[J][i - 1] + info[a][i - 1] * info[b][i]
    print(info[0][m] % (10 ** 9 + 7))
t = int(input())
for i in range(t):
    (n, m) = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]
    process(A, m)

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def f(u, v):
    return u * n + v

def g(u, v):
    return u * m + v

def sparse_table(a):
    table = []
    (s0, l) = (a, 1)
    table.append(s0)
    while 2 * l <= len(a):
        s = [max(s0[i], s0[i + l]) for i in range(len(s0) - l)]
        table.append(list(s))
        s0 = s
        l *= 2
    return table

def get_max(l, r, table):
    d = (r - l + 1).bit_length() - 1
    ans = max(table[d][l], table[d][r - pow2[d] + 1])
    return ans

def make_graph(n, m):
    s = [0] * (n + 3)
    for i in range(0, 2 * m, 2):
        s[x[i] + 2] += 1
    for i in range(2, n + 3):
        s[i] += s[i - 1]
    G = [0] * m
    for i in range(0, 2 * m, 2):
        j = x[i] + 1
        G[s[j]] = x[i ^ 1]
        s[j] += 1
    return (G, s)
t = int(input())
ans = []
mod = pow(10, 9) + 7
pow2 = [1]
for _ in range(20):
    pow2.append(2 * pow2[-1])
for _ in range(t):
    (n, m) = map(int, input().split())
    a = list(map(int, input().split()))
    ma = sparse_table([f(a[i], n - i - 1) for i in range(n)])
    (q, e, p) = ([f(0, n - 1)], [], [-1])
    for k in range(n):
        (l, r) = divmod(q[k], n)
        u = n - get_max(l, r, ma) % n - 1
        e.append(u)
        if l ^ u:
            q.append(f(l, u - 1))
            p.append(u)
        if u ^ r:
            q.append(f(u + 1, r))
            p.append(u)
    x = [0] * (2 * (n - 1))
    for i in range(n - 1):
        (x[2 * i], x[2 * i + 1]) = (p[i + 1], e[i + 1])
    (G, s0) = make_graph(n, n - 1)
    dp = [1] * ((n + 1) * m)
    for i in range(m):
        dp[g(n, i)] = 0
    for i in e[::-1]:
        if s0[i] == s0[i + 1]:
            continue
        if s0[i + 1] - s0[i] == 1:
            (l, r) = (G[s0[i]], n)
            if l > i:
                (l, r) = (r, l)
        else:
            (l, r) = (G[s0[i]], G[s0[i] + 1])
        (cl, cr) = (l // n, r // n)
        for j in range(m):
            cr = (cr + dp[g(r, j)]) % mod
            dp[g(i, j)] = cl * cr % mod
            cl = (cl + dp[g(l, j)]) % mod
    (l, r) = (e[0] * m, (e[0] + 1) * m)
    ans0 = sum(dp[l:r]) % mod
    ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))