解题思路
核心改法：先做标准 LIS 分层，只在“能位于某条 LIS 上”的位置里连边，然后在相邻层之间用“值严格递增 + 位置可衔接”的条件建图，最后在“值节点”上做 DP，并且在每一层对相同数值合并（去重）。
具体步骤：
-
计算每个位置 i 的
L[i]：以 a[i] 结尾的 LIS 长度（从左到右、值严格小于）。
P3894.第4题-小美的最长上升子序列
题目内容
给定一个长度为n的数组a，请你计算其中所有本质不同最长上升子序列的数量。由于答案可能非常大，请将结果对998244353取模后输出。
**[子序列]**如果一个序列可以通过删除原序列的若干(可能为零)元素得到，则称前者为后者的一个子序列。
**[上升序列]**我们称s为一个上升序列，当且仅当其中任意相邻元素满足si<si+1
**[本质不同序列]**若两个序列的长度不同，或在某一位置上的元素不同，则认为它们是不同的序列。
输入描述
每个测试文件均包含多组测试数据。
第一行输入一个整数T(1≤T≤104)代表数据组数，每组测试数据描述如下:
第一行输入一个正整数n(1≤n≤2⋅105)，代表数组a的长度。
第二行输入n个正整数a1,a2,...,an(1≤ai≤109),代表a中的元素。
除此之外，保证单个测试文件的n之和不超过2×105。
输出描述
对于每组测试数据，输出一行一个整数，代表数组a中本质不同
最长上升了序列的数量，对998244353取模后的结果。
样例1
输入
5
1
1
2
1 1
6
1 1 4 5 1 4
7
3 2 2 4 5 8 7
7
1 9 1 9 8 1 0
输出
1
1
1
4
2
说明
在最后一组测试数据中，两个本质不同最长上升子序列分别为{1,9}和{1,8}
