Top-Notch Insertions (Codeforces 1561F)
Tags: Others, combinatorics

Consider the insertion sort algorithm used to sort an integer sequence $$$[a_1, a_2, \ldots, a_n]$$$ of length $$$n$$$ in non-decreasing order.For each $$$i$$$ in order from $$$2$$$ to $$$n$$$, do the following. If $$$a_i \ge a_{i-1}$$$, do nothing and move on to the next value of $$$i$$$. Otherwise, find the smallest $$$j$$$ such that $$$a_i < a_j$$$, shift the elements on positions from $$$j$$$ to $$$i-1$$$ by one position to the right, and write down the initial value of $$$a_i$$$ to position $$$j$$$. In this case we'll say that we performed an insertion of an element from position $$$i$$$ to position $$$j$$$.It can be noticed that after processing any $$$i$$$, the prefix of the sequence $$$[a_1, a_2, \ldots, a_i]$$$ is sorted in non-decreasing order, therefore, the algorithm indeed sorts any sequence.For example, sorting $$$[4, 5, 3, 1, 3]$$$ proceeds as follows:   $$$i = 2$$$: $$$a_2 \ge a_1$$$, do nothing;  $$$i = 3$$$: $$$j = 1$$$, insert from position $$$3$$$ to position $$$1$$$: $$$[3, 4, 5, 1, 3]$$$;  $$$i = 4$$$: $$$j = 1$$$, insert from position $$$4$$$ to position $$$1$$$: $$$[1, 3, 4, 5, 3]$$$;  $$$i = 5$$$: $$$j = 3$$$, insert from position $$$5$$$ to position $$$3$$$: $$$[1, 3, 3, 4, 5]$$$. You are given an integer $$$n$$$ and a list of $$$m$$$ integer pairs $$$(x_i, y_i)$$$. We are interested in sequences such that if you sort them using the above algorithm, exactly $$$m$$$ insertions will be performed: first from position $$$x_1$$$ to position $$$y_1$$$, then from position $$$x_2$$$ to position $$$y_2$$$, ..., finally, from position $$$x_m$$$ to position $$$y_m$$$.How many sequences of length $$$n$$$ consisting of (not necessarily distinct) integers between $$$1$$$ and $$$n$$$, inclusive, satisfy the above condition? Print this number modulo $$$998\,244\,353$$$.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). Description of the test cases follows.The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$0 \le m < n$$$) — the length of the sequence and the number of insertions.The $$$i$$$-th of the following $$$m$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$2 \le x_1 < x_2 < \ldots < x_m \le n$$$; $$$1 \le y_i < x_i$$$). These lines describe the sequence of insertions in chronological order.It is guaranteed that the sum of $$$m$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$. Note that there is no constraint on the sum of $$$n$$$ of the same kind.

Output: For each test case, print the number of sequences of length $$$n$$$ consisting of integers from $$$1$$$ to $$$n$$$ such that sorting them with the described algorithm produces the given sequence of insertions, modulo $$$998\,244\,353$$$.

Note: In the first test case, the algorithm performs no insertions — therefore, the initial sequence is already sorted in non-decreasing order. There are $$$10$$$ such sequences: $$$[1, 1, 1], [1, 1, 2], [1, 1, 3], [1, 2, 2], [1, 2, 3], [1, 3, 3], [2, 2, 2], [2, 2, 3], [2, 3, 3], [3, 3, 3]$$$.In the second test case, the only sequence satisfying the conditions is $$$[3, 2, 1]$$$.In the third test case, $$$[4, 5, 3, 1, 3]$$$ is one of the sought sequences.

Sample Inputs:
3
3 0
3 2
2 1
3 1
5 3
3 1
4 1
5 3

Sample Outputs:
10
1
21

Solution (Python):
import sys
M = 998244353
MAX = 200005
inv = [1] * MAX
MM = 2 * MAX
fac = [1] * MM
fen = [0] * MM

def add(n, i):
    while n < MM:
        fen[n] += i
        n += n & -n
pl = [1 << i for i in range(19, -1, -1)]

def kth(n):
    j = 0
    for i in pl:
        if j + i < MM and fen[j + i] < n:
            j += i
            n -= fen[j]
    return j + 1
for i in range(2, MM):
    fac[i] = i * fac[i - 1] % M
for i in range(1, MM):
    add(i, 1)
for i in range(2, MAX):
    inv[i] = (M - M // i) * inv[M % i] % M
for i in range(2, MAX):
    inv[i] = inv[i] * inv[i - 1] % M
for _ in range(int(sys.stdin.readline())):
    (n, m) = [int(i) for i in sys.stdin.readline().split()]
    c = 0
    (x, y) = ([], [])
    for i in range(m):
        x.append(int(sys.stdin.readline().split()[1]))
    y = []
    for i in x[::-1]:
        (a, b) = (kth(i), kth(i + 1))
        if a == b - 1:
            c += 1
        add(a, -1)
        y.append(a)
    for i in y:
        add(i, 1)
    sys.stdout.write('%d\n' % (fac[n + n - 1 - c] * inv[n] * inv[n - 1 - c] % M))

Solution (Python):
class SegmentTree:

    def __init__(self, init_val, segfunc, ide_ele):
        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
        self.size = n
        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 += 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 bisect(self, S):
        pos = 1
        if self.tree[1] < S:
            return self.num
        while pos < self.num:
            (l, r) = (2 * pos, 2 * pos + 1)
            if S <= self.tree[l]:
                pos = 2 * pos
            else:
                S -= self.tree[l]
                pos = 2 * pos + 1
        return pos - self.num
import sys, random, bisect
from collections import deque, defaultdict
from heapq import heapify, heappop, heappush
from itertools import permutations
from math import gcd, log
input = lambda : sys.stdin.buffer.readline()

def cmb(n, r, mod):
    if r < 0 or r > n:
        return 0
    return g1[n] * g2[r] % mod * g2[n - r] % mod
mod = 998244353
N = 5 * 10 ** 5
g1 = [1] * (N + 1)
g2 = [1] * (N + 1)
inverse = [1] * (N + 1)
for i in range(2, N + 1):
    g1[i] = g1[i - 1] * i % mod
    inverse[i] = -inverse[mod % i] * (mod // i) % mod
    g2[i] = g2[i - 1] * inverse[i] % mod
inverse[0] = 0

def merge(A0, A1):
    (Y0, S0) = A0
    (Y1, S1) = A1
    if not Y0:
        return A1
    if not Y1:
        return A0
    Y2 = Y0 + Y1
    cnt = 0
    idx = 0
    n = len(S0)
    T = [S0[0]] + [S0[i + 1] - S0[i] for i in range(n - 1)]
    Seg = SegmentTree(T, lambda x, y: x + y, 0)
    for y in Y1:
        idx = Seg.bisect(y - 1)
        if idx != Seg.num:
            Seg.update(idx, 1)
    S0 = [Seg.tree[Seg.num + i] for i in range(n)]
    for i in range(1, n):
        S0[i] += S0[i - 1]
    S1 = S1[::-1]
    S2 = []
    for i in range(n):
        while S1:
            if S1[-1] < S0[i]:
                S2.append(S1.pop())
            elif S1[-1] == S0[i]:
                S1.pop()
            else:
                break
        S2.append(S0[i])
    S1 = S1[::-1]
    S2 += S1
    return [Y2, S2]
for _ in range(int(input())):
    (n, m) = map(int, input().split())
    init = [[] for i in range(m)]
    tS = []
    k = n // 5
    for i in range(m):
        (x, y) = map(int, input().split())
        init[i] = [[y + 1], [y + 1]]
    Seg = SegmentTree(init, merge, [[], []])
    (Y, S) = Seg.tree[1]
    k = len(S) + 1
    print(cmb(n - k + n, n, mod))

Solution (Python):
class SegmentTree:

    def __init__(self, init_val, segfunc, ide_ele):
        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
        self.size = n
        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 += 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 bisect(self, S):
        pos = 1
        if self.tree[1] < S:
            return self.num
        while pos < self.num:
            (l, r) = (2 * pos, 2 * pos + 1)
            if S <= self.tree[l]:
                pos = 2 * pos
            else:
                S -= self.tree[l]
                pos = 2 * pos + 1
        return pos - self.num
import sys, random, bisect
from collections import deque, defaultdict
from heapq import heapify, heappop, heappush
from itertools import permutations
from math import gcd, log
input = lambda : sys.stdin.buffer.readline()

def cmb(n, r, mod):
    if r < 0 or r > n:
        return 0
    return g1[n] * g2[r] % mod * g2[n - r] % mod
mod = 998244353
N = 5 * 10 ** 5
g1 = [1] * (N + 1)
g2 = [1] * (N + 1)
inverse = [1] * (N + 1)
for i in range(2, N + 1):
    g1[i] = g1[i - 1] * i % mod
    inverse[i] = -inverse[mod % i] * (mod // i) % mod
    g2[i] = g2[i - 1] * inverse[i] % mod
inverse[0] = 0

def merge(A0, A1):
    (Y0, S0) = A0
    (Y1, S1) = A1
    if not Y0:
        return A1
    if not Y1:
        return A0
    Y2 = Y0 + Y1
    cnt = 0
    idx = 0
    n = len(S0)
    T = [S0[0]] + [S0[i + 1] - S0[i] for i in range(n - 1)]
    Seg = SegmentTree(T, lambda x, y: x + y, 0)
    for y in Y1:
        idx = Seg.bisect(y - 1)
        if idx != Seg.num:
            Seg.update(idx, 1)
    S0 = [Seg.tree[Seg.num + i] for i in range(n)]
    for i in range(1, n):
        S0[i] += S0[i - 1]
    S1 = S1[::-1]
    S2 = []
    for i in range(n):
        while S1:
            if S1[-1] < S0[i]:
                S2.append(S1.pop())
            elif S1[-1] == S0[i]:
                S1.pop()
            else:
                break
        S2.append(S0[i])
    S1 = S1[::-1]
    S2 += S1
    return [Y2, S2]
for _ in range(int(input())):
    (n, m) = map(int, input().split())
    init = [[] for i in range(m)]
    tS = []
    k = n // 5
    for i in range(m):
        (x, y) = map(int, input().split())
        init[i] = [[y + 1], [y + 1]]
    Seg = SegmentTree(init, merge, [[], []])
    (Y, S) = Seg.tree[1]
    k = len(S) + 1
    print(cmb(n - k + n, n, mod))