Identify the Operations (Codeforces 1442B)
Tags: Greedy, dsu

We start with a permutation $$$a_1, a_2, \ldots, a_n$$$ and with an empty array $$$b$$$. We apply the following operation $$$k$$$ times.On the $$$i$$$-th iteration, we select an index $$$t_i$$$ ($$$1 \le t_i \le n-i+1$$$), remove $$$a_{t_i}$$$ from the array, and append one of the numbers $$$a_{t_i-1}$$$ or $$$a_{t_i+1}$$$ (if $$$t_i-1$$$ or $$$t_i+1$$$ are within the array bounds) to the right end of the array $$$b$$$. Then we move elements $$$a_{t_i+1}, \ldots, a_n$$$ to the left in order to fill in the empty space.You are given the initial permutation $$$a_1, a_2, \ldots, a_n$$$ and the resulting array $$$b_1, b_2, \ldots, b_k$$$. All elements of an array $$$b$$$ are distinct. Calculate the number of possible sequences of indices $$$t_1, t_2, \ldots, t_k$$$ modulo $$$998\,244\,353$$$.

Input: Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \le t \le 100\,000$$$), denoting the number of test cases, followed by a description of the test cases.The first line of each test case contains two integers $$$n, k$$$ ($$$1 \le k < n \le 200\,000$$$): sizes of arrays $$$a$$$ and $$$b$$$.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$): elements of $$$a$$$. All elements of $$$a$$$ are distinct.The third line of each test case contains $$$k$$$ integers $$$b_1, b_2, \ldots, b_k$$$ ($$$1 \le b_i \le n$$$): elements of $$$b$$$. All elements of $$$b$$$ are distinct.The sum of all $$$n$$$ among all test cases is guaranteed to not exceed $$$200\,000$$$.

Output: For each test case print one integer: the number of possible sequences modulo $$$998\,244\,353$$$.

Note: $$$\require{cancel}$$$Let's denote as $$$a_1 a_2 \ldots \cancel{a_i} \underline{a_{i+1}} \ldots a_n \rightarrow a_1 a_2 \ldots a_{i-1} a_{i+1} \ldots a_{n-1}$$$ an operation over an element with index $$$i$$$: removal of element $$$a_i$$$ from array $$$a$$$ and appending element $$$a_{i+1}$$$ to array $$$b$$$.In the first example test, the following two options can be used to produce the given array $$$b$$$:  $$$1 2 \underline{3} \cancel{4} 5 \rightarrow 1 \underline{2} \cancel{3} 5 \rightarrow 1 \cancel{2} \underline{5} \rightarrow 1 2$$$; $$$(t_1, t_2, t_3) = (4, 3, 2)$$$;  $$$1 2 \underline{3} \cancel{4} 5 \rightarrow \cancel{1} \underline{2} 3 5 \rightarrow 2 \cancel{3} \underline{5} \rightarrow 1 5$$$; $$$(t_1, t_2, t_3) = (4, 1, 2)$$$. In the second example test, it is impossible to achieve the given array no matter the operations used. That's because, on the first application, we removed the element next to $$$4$$$, namely number $$$3$$$, which means that it couldn't be added to array $$$b$$$ on the second step.In the third example test, there are four options to achieve the given array $$$b$$$:  $$$1 4 \cancel{7} \underline{3} 6 2 5 \rightarrow 1 4 3 \cancel{6} \underline{2} 5 \rightarrow \cancel{1} \underline{4} 3 2 5 \rightarrow 4 3 \cancel{2} \underline{5} \rightarrow 4 3 5$$$; $$$1 4 \cancel{7} \underline{3} 6 2 5 \rightarrow 1 4 3 \cancel{6} \underline{2} 5 \rightarrow 1 \underline{4} \cancel{3} 2 5 \rightarrow 1 4 \cancel{2} \underline{5} \rightarrow 1 4 5$$$; $$$1 4 7 \underline{3} \cancel{6} 2 5 \rightarrow 1 4 7 \cancel{3} \underline{2} 5 \rightarrow \cancel{1} \underline{4} 7 2 5 \rightarrow 4 7 \cancel{2} \underline{5} \rightarrow 4 7 5$$$; $$$1 4 7 \underline{3} \cancel{6} 2 5 \rightarrow 1 4 7 \cancel{3} \underline{2} 5 \rightarrow 1 \underline{4} \cancel{7} 2 5 \rightarrow 1 4 \cancel{2} \underline{5} \rightarrow 1 4 5$$$;

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

Sample Outputs:
2
0
4

Solution (Python):
from sys import stdin, setrecursionlimit
input = stdin.readline
import threading
setrecursionlimit(10 ** 7)
mod = 998244353

def add(a, b):
    return (a % mod + b % mod) % mod

def solve(i, took):
    if i == k:
        return 1
    if dp[i][took] != -1:
        return dp[i][took]
    ans = 0
    ind = da[b[i]]
    if ind != 0 and db[a[ind - 1]] < i:
        ans = add(ans, solve(i + 1, 0))
    ind = da[b[i]]
    if ind != n - 1 and db[a[ind + 1]] < i:
        ans = add(ans, solve(i + 1, 1))
    dp[i][took] = ans
    return ans

def answer():
    global dp
    dp = [[-1, -1] for i in range(k)]
    ans = solve(0, 0)
    return ans
(n, k, a, b, dp, da, db) = (None, None, None, None, None, None, None)

def main():
    global n, k, a, b, dp, da, db
    for T in range(int(input())):
        (n, k) = map(int, input().split())
        a = list(map(int, input().split()))
        b = list(map(int, input().split()))
        dp = None
        da = [-1] * (n + 1)
        for i in range(n):
            da[a[i]] = i
        db = [-1] * (n + 1)
        for i in range(k):
            db[b[i]] = i
        print(answer())
if __name__ == '__main__':
    threading.stack_size(10 ** 8)
    threading.Thread(target=main).start()

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
    return int(sys.stdin.buffer.readline())

def MI():
    return map(int, sys.stdin.buffer.readline().split())

def LI():
    return list(map(int, sys.stdin.buffer.readline().split()))

def LLI(rows_number):
    return [LI() for _ in range(rows_number)]

def BI():
    return sys.stdin.buffer.readline().rstrip()

def SI():
    return sys.stdin.buffer.readline().rstrip().decode()
md = 998244353
for _ in range(II()):
    (n, k) = MI()
    aa = LI()
    bb = LI()
    atoi = [0] * (n + 1)
    for (i, a) in enumerate(aa):
        atoi[a] = i
    fin = [0] * (n + 2)
    fin[n] = fin[n + 1] = 1
    ans = 1
    for b in bb[::-1]:
        i = atoi[b]
        ans *= 2 - fin[i - 1] - fin[i + 1]
        ans %= md
        fin[i] = 1
    print(ans)

Solution (Python):
test_cases = int(input())
for i in range(test_cases):
    (a_len, b_len) = map(int, input().split())
    a_first = 0
    a_last = a_len - 1
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    a_map = {}
    for (idx, val) in enumerate(a):
        a_map[val] = idx
    b_set = set(b)
    branches = 0
    for val in b:
        idx = a_map[val]
        left = False
        if idx > a_first and a[idx - 1] not in b_set:
            left = True
        right = False
        if idx < a_last and a[idx + 1] not in b_set:
            right = True
        if left or right:
            b_set.remove(val)
            if left and right:
                branches += 1
        else:
            branches = -1
            break
    print(2 ** branches % 998244353) if branches > -1 else print(0)