A16645. Looking at Towers (difficult version)
编程题
提高+/省选-
知识点
题目描述
这是本题的困难版本。简单版本与困难版本的唯一区别在于 $t$ 和 $n$ 的数据范围。
现有一排 $m$ 个塔，第 $i$ 个塔的高度为 $h_i$。
如果你从左边看这排塔，则会看到所有比前面所有塔都高的塔。同样地，如果你从右边看这排塔，则会看到所有比后面所有塔都高的塔。例如，如果这排塔的高度为 $[3, 5, 5, 7, 4, 6, 7, 2, 4]$，那么：
- 从左边看，可以看到高度为 $3$、$5$ 和 $7$ 的塔；
- 从右边看，可以看到高度为 $7$ 和 $4$ 的塔。
记 $L(h)$ 为从左边看到的高度集合，$R(h)$ 为从右边看到的高度集合，其中 $h$ 是当前的高度序列。以上述例子为例：$L(h) = \{3, 5, 7\}$，$R(h) = \{4, 7\}$。
你有一个序列 $a_1, a_2, \dots, a_n$。你的任务是计算有多少个 $a$ 的子序列 $a'$ 满足 $L(a) = L(a')$ 且 $R(a) = R(a')$，其中 $a'$ 是你考虑的子序列。只要选择的元素下标不同，子序列就被认为是不同的。
现有一排 $m$ 个塔，第 $i$ 个塔的高度为 $h_i$。
如果你从左边看这排塔，则会看到所有比前面所有塔都高的塔。同样地，如果你从右边看这排塔，则会看到所有比后面所有塔都高的塔。例如，如果这排塔的高度为 $[3, 5, 5, 7, 4, 6, 7, 2, 4]$，那么：
- 从左边看，可以看到高度为 $3$、$5$ 和 $7$ 的塔；
- 从右边看，可以看到高度为 $7$ 和 $4$ 的塔。
记 $L(h)$ 为从左边看到的高度集合，$R(h)$ 为从右边看到的高度集合，其中 $h$ 是当前的高度序列。以上述例子为例：$L(h) = \{3, 5, 7\}$，$R(h) = \{4, 7\}$。
你有一个序列 $a_1, a_2, \dots, a_n$。你的任务是计算有多少个 $a$ 的子序列 $a'$ 满足 $L(a) = L(a')$ 且 $R(a) = R(a')$，其中 $a'$ 是你考虑的子序列。只要选择的元素下标不同，子序列就被认为是不同的。
输入格式
第一行输入一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。
每组测试包括两行：
- 第一行一个整数 $n$（$1 \leq n \leq 3 \cdot 10^5$）；
- 第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^9$）。
输入还保证：所有测试的数据中，$n$ 的总和不超过 $3 \cdot 10^5$。
每组测试包括两行：
- 第一行一个整数 $n$（$1 \leq n \leq 3 \cdot 10^5$）；
- 第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^9$）。
输入还保证：所有测试的数据中，$n$ 的总和不超过 $3 \cdot 10^5$。
输出格式
对于每组测试，输出一个整数，表示满足条件的子序列数量。由于答案可能很大，请输出对 $998244353$ 取模后的结果。
输入输出样例
输入 #1
5 5 4 2 4 8 3 5 1 2 3 2 1 6 1 2 3 3 2 1 9 3 5 5 7 4 6 7 2 4 1 10
输出 #1
5 1 3 51 1
说明/提示
在第一个样例中，$L(a) = \{4, 8\}$，$R(a) = \{3, 8\}$。被计入答案的子序列有：
- $[4, 8, 3]$（第 $1$、$4$、$5$ 个元素）；
- $[4, 8, 3]$（第 $3$、$4$、$5$ 个元素）；
- $[4, 2, 8, 3]$（第 $1$、$2$、$4$、$5$ 个元素）；
- $[4, 4, 8, 3]$（第 $1$、$3$、$4$、$5$ 个元素）；
- $[4, 2, 4, 8, 3]$（整段序列）。
在第二个样例中，唯一合法的子序列是整个序列本身。
- $[4, 8, 3]$（第 $1$、$4$、$5$ 个元素）；
- $[4, 8, 3]$（第 $3$、$4$、$5$ 个元素）；
- $[4, 2, 8, 3]$（第 $1$、$2$、$4$、$5$ 个元素）；
- $[4, 4, 8, 3]$（第 $1$、$3$、$4$、$5$ 个元素）；
- $[4, 2, 4, 8, 3]$（整段序列）。
在第二个样例中，唯一合法的子序列是整个序列本身。