解题思路

核心改法：先做标准 LIS 分层，只在“能位于某条 LIS 上”的位置里连边，然后在相邻层之间用“值严格递增 + 位置可衔接”的条件建图，最后在“值节点”上做 DP，并且在每一层对相同数值合并（去重）。

具体步骤：

1. 计算每个位置 i 的

   • L[i]：以 a[i] 结尾的 LIS 长度（从左到右、值严格小于）。
   • R[i]：以 a[i] 开始的 LIS 长度（从右到左、值严格大于）。 令 L* = max(L[i])。

2. 只保留“在某条 LIS 上”的位置：L[i] + R[i] - 1 == L*。把这些位置按 L[i] 分到层 1..L*。

3. 对于每一层 ℓ，按数值去重：对同一数值 v，记录它在该层中的

   • minPosℓ[v]：最早出现位置
   • maxPosℓ[v]：最晚出现位置

4. 在层 ℓ-1 → ℓ 之间建立“值节点”的可达性（是否存在一条边 u→v）：

   • 必须 u < v（严格递增），且存在位置 j 在层 ℓ-1 的值 u 与位置 i 在层 ℓ 的值 v 使得 j < i。
   • 这等价于：maxPosℓ[v] > minPosℓ-1[u]（层内合并后，这个充要条件很好验证）。

5. 计数 DP（对“值”去重）：

   • 第 1 层所有不同值的方案数 dp₁[v] = 1。
   • 对 ℓ = 2..L*，有

   

   • 为了高效，做一个二维离线支配统计：把上一层的每个 u 视作点 ，当前层每个 v 的查询是：“求所有 value<u 且 $key$ ≤ $maxPos_{\ell}[v]-1$ 的 dp 之和”。 实现上：按 key（即 minPos）从小到大扫描，把满足阈值的 u 的 dp 加入按值有序的树状数组（Fenwick），然后对 v 查询前缀（小于 v 的所有值）的和即可。 这样每层是 O(k log M)（k 为该层不同值个数，M 为不同值总数），总体 O(n log n)。

6. 答案是最后一层所有 dp_{L*}[v] 的和（取模 998244353）。 这个流程天然去重：同一数值在同一层的所有位置被合并成一个“值节点”，因此不会把“相同数值序列”重复计算。并且分层确保了整条链的位置序号可衔接，杜绝了之前的错误。

用你的样例 1 3 2 4 3：

• L* = 3；在三层上去重后可得 层1：{1}，层2：{2,3}，层3：{3,4}（按值去重且位置可达）
• 逐层 DP 得到三条不同的值序列：{1,2,3}、{1,2,4}、{1,3,4} ⇒ 输出 3。

复杂度分析

• 计算 L[i], R[i]：O(n log n)（值域压缩 + 树状数组/线段树）。
• 每层的二维离线计数：合计 O(n log n)。
• 空间：O(n)。

代码实现

Python

# -*- coding: utf-8 -*-
import sys
from collections import defaultdict

MOD = 998244353

class BITMax:
    # 维护前缀最大值（用于求 L[i]/R[i]）
    def __init__(self, n):
        self.n = n
        self.t = [0]*(n+1)
    def update(self, i, v):
        while i<=self.n:
            if v>self.t[i]:
                self.t[i]=v
            i += i & -i
    def query(self, i):
        res = 0
        while i>0:
            if self.t[i]>res: res = self.t[i]
            i -= i & -i
        return res

class BITSum:
    # 维护前缀和（用于分层的二维离线：值维度）
    def __init__(self, n):
        self.n = n
        self.t = [0]*(n+1)
    def add(self, i, v):
        while i<=self.n:
            self.t[i] = (self.t[i] + v) % MOD
            i += i & -i
    def sum(self, i):
        res = 0
        while i>0:
            res += self.t[i]; res %= MOD
            i -= i & -i
        return res

def solve():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    T = next(it)
    out = []
    for _ in range(T):
        n = next(it)
        a = [next(it) for _ in range(n)]
        # 值压缩
        xs = sorted(set(a)); m = len(xs)
        rk = {v:i+1 for i,v in enumerate(xs)}
        A = [rk[x] for x in a]

        # L[i]：以 i 结尾的 LIS 长度（值严格小于）
        bit = BITMax(m)
        L = [0]*n
        for i in range(n):
            L[i] = bit.query(A[i]-1) + 1
            bit.update(A[i], L[i])

        # R[i]：以 i 开始的 LIS 长度（值严格大于）
        bit = BITMax(m)
        R = [0]*n
        for i in range(n-1, -1, -1):
            # 查询值> A[i] 等价于查询“反向坐标”的前缀
            rev = m - A[i]
            best = bit.query(rev)  # 在更大的值上接
            R[i] = best + 1
            bit.update(m - A[i] + 1, R[i])

        Lstar = max(L)

        # 只保留位于某条 LIS 上的点
        layers_pos = [[] for _ in range(Lstar+1)]  # 1..L*
        for i in range(n):
            if L[i] + R[i] - 1 == Lstar:
                layers_pos[L[i]].append(i)

        # 每层按“值去重”，并记录该层同值的 (minPos, maxPos)
        # 用值的压缩序 rkVal（1..m）作为键
        layer_vals = [dict() for _ in range(Lstar+1)]
        for ℓ in range(1, Lstar+1):
            mp = {}
            for i in layers_pos[ℓ]:
                v = A[i]
                if v not in mp: mp[v] = [i+1, i+1]  # 1-based 位置
                else:
                    mp[v][0] = min(mp[v][0], i+1)
                    mp[v][1] = max(mp[v][1], i+1)
            layer_vals[ℓ] = mp  # v -> [minPos, maxPos]

        # 分层 DP（对值去重），层1为 1
        dp_prev = {}
        for v in layer_vals[1].keys():
            dp_prev[v] = 1

        for ℓ in range(2, Lstar+1):
            prev_items = []
            for u, (mn, _) in layer_vals[ℓ-1].items():
                prev_items.append((mn, u, dp_prev.get(u, 0)))  # (minPos, value, ways)
            prev_items.sort()  # 按 minPos 升序

            cur_items = []
            for v, (_, mx) in layer_vals[ℓ].items():
                cur_items.append((mx-1, v))  # 允许 j < i 等价于 minPos ≤ maxPos-1
            cur_items.sort()  # 按阈值升序

            bit_sum = BITSum(m)
            j = 0
            dp_cur = {}
            for thr, v in cur_items:
                while j < len(prev_items) and prev_items[j][0] <= thr:
                    _, u, ways = prev_items[j]
                    if ways:
                        bit_sum.add(u, ways)  # 值维度是 u 的秩
                    j += 1
                # 只允许 u < v
                dp_cur[v] = bit_sum.sum(v-1)
            dp_prev = dp_cur

        ans = sum(dp_prev.values()) % MOD
        out.append(str(ans))
    print("\n".join(out))

if __name__ == "__main__":
    solve()

Java

import java.io.*;
import java.util.*;

/* 修正版：分层去重 + 相邻层二维离线 + 树状数组 */
public class Main {
    static final int MOD = 998244353;

    static class BITMax {
        int n; int[] t;
        BITMax(int n){ this.n=n; t=new int[n+1]; }
        void update(int i,int v){ for(; i<=n; i+=i&-i) t[i]=Math.max(t[i], v); }
        int query(int i){ int res=0; for(; i>0; i-=i&-i) res=Math.max(res,t[i]); return res; }
    }
    static class BITSum {
        int n; int[] t;
        BITSum(int n){ this.n=n; t=new int[n+1]; }
        void add(int i,int v){ for(; i<=n; i+=i&-i){ int x=t[i]+v; if(x>=MOD)x-=MOD; t[i]=x; } }
        int sum(int i){ int res=0; for(; i>0; i-=i&-i){ res+=t[i]; if(res>=MOD)res-=MOD; } return res; }
    }

    static class FastScanner {
        final InputStream in; final byte[] buf = new byte[1<<16];
        int ptr=0, len=0; FastScanner(InputStream is){ in=is; }
        int read() throws IOException {
            if(ptr>=len){ len=in.read(buf); ptr=0; if(len<=0) return -1; }
            return buf[ptr++];
        }
        int nextInt() throws IOException {
            int c, s=1, x=0; do{ c=read(); }while(c<=32);
            if(c=='-'){ s=-1; c=read(); }
            for(; c>32; c=read()) x = x*10 + (c-'0');
            return x*s;
        }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        StringBuilder out = new StringBuilder();
        int T = fs.nextInt();
        while (T-- > 0) {
            int n = fs.nextInt();
            int[] a = new int[n];
            for (int i=0;i<n;i++) a[i]=fs.nextInt();

            // 值压缩
            int[] b = a.clone(); Arrays.sort(b);
            int m=0; for(int i=0;i<n;i++) if(i==0 || b[i]!=b[i-1]) b[m++]=b[i];
            int[] vals = Arrays.copyOf(b, m);
            int[] A = new int[n];
            for (int i=0;i<n;i++){
                int v = Arrays.binarySearch(vals, a[i]);
                A[i] = v+1; // 1-based rank
            }

            // L[i]
            int[] L = new int[n];
            BITMax bit = new BITMax(m);
            for (int i=0;i<n;i++){
                L[i] = bit.query(A[i]-1) + 1;
                bit.update(A[i], L[i]);
            }

            // R[i]
            int[] R = new int[n];
            bit = new BITMax(m);
            for (int i=n-1;i>=0;i--){
                int rev = m - A[i];
                int best = bit.query(rev);
                R[i] = best + 1;
                bit.update(m - A[i] + 1, R[i]);
            }

            int Lstar = 0; for(int x: L) Lstar = Math.max(Lstar, x);

            // 分层保留在某条 LIS 上的位置
            ArrayList<Integer>[] layerPos = new ArrayList[Lstar+1];
            for (int i=0;i<=Lstar;i++) layerPos[i]=new ArrayList<>();
            for (int i=0;i<n;i++) if (L[i]+R[i]-1==Lstar) layerPos[L[i]].add(i);

            // 每层按值去重并记录 (minPos, maxPos)
            HashMap<Integer,int[]>[] layerVals = new HashMap[Lstar+1];
            for (int ℓ=1; ℓ<=Lstar; ℓ++){
                HashMap<Integer,int[]> mp = new HashMap<>();
                for (int idx: layerPos[ℓ]){
                    int v = A[idx];
                    int pos = idx+1;
                    int[] p = mp.get(v);
                    if (p==null){ mp.put(v, new int[]{pos,pos}); }
                    else { p[0]=Math.min(p[0],pos); p[1]=Math.max(p[1],pos); }
                }
                layerVals[ℓ]=mp;
            }

            // 层 1
            HashMap<Integer,Integer> dpPrev = new HashMap<>();
            for (int v: layerVals[1].keySet()) dpPrev.put(v, 1);

            // 层间 DP
            for (int ℓ=2; ℓ<=Lstar; ℓ++){
                // prev_items: (minPos, value, ways)
                int szPrev = layerVals[ℓ-1].size();
                int[][] prevItems = new int[szPrev][3];
                int p=0;
                for (Map.Entry<Integer,int[]> e: layerVals[ℓ-1].entrySet()){
                    int u = e.getKey();
                    int mn = e.getValue()[0];
                    int ways = dpPrev.getOrDefault(u, 0);
                    prevItems[p++]=new int[]{mn, u, ways};
                }
                Arrays.sort(prevItems, Comparator.comparingInt(x->x[0]));

                // cur_items: (threshold=maxPos-1, value)
                int szCur = layerVals[ℓ].size();
                int[][] curItems = new int[szCur][2];
                p=0;
                for (Map.Entry<Integer,int[]> e: layerVals[ℓ].entrySet()){
                    int v = e.getKey();
                    int mx = e.getValue()[1];
                    curItems[p++]=new int[]{mx-1, v};
                }
                Arrays.sort(curItems, Comparator.comparingInt(x->x[0]));

                BITSum bitSum = new BITSum(m);
                HashMap<Integer,Integer> dpCur = new HashMap<>();
                int j=0;
                for (int[] q : curItems){
                    int thr = q[0], v = q[1];
                    while (j<prevItems.length && prevItems[j][0] <= thr){
                        int u = prevItems[j][1];
                        int ways = prevItems[j][2];
                        if (ways!=0) bitSum.add(u, ways);
                        j++;
                    }
                    // u < v
                    int waysV = bitSum.sum(v-1);
                    dpCur.put(v, waysV);
                }
                dpPrev = dpCur;
            }

            long ans = 0;
            for (int w: dpPrev.values()){ ans += w; if (ans>=MOD) ans-=MOD; }
            out.append(ans%MOD).append('\n');
        }
        System.out.print(out);
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;

struct BITMax {
    int n; vector<int> t;
    BITMax(int n=0){ init(n); }
    void init(int n_){ n=n_; t.assign(n+1, 0); }
    void update(int i,int v){ for(; i<=n; i+=i&-i) t[i]=max(t[i], v); }
    int query(int i){ int res=0; for(; i>0; i-=i&-i) res=max(res, t[i]); return res; }
};
struct BITSum {
    int n; vector<int> t;
    BITSum(int n=0){ init(n); }
    void init(int n_){ n=n_; t.assign(n+1, 0); }
    void add(int i,int v){ for(; i<=n; i+=i&-i){ int x=t[i]+v; if(x>=MOD)x-=MOD; t[i]=x; } }
    int sum(int i){ int res=0; for(; i>0; i-=i&-i){ res+=t[i]; if(res>=MOD)res-=MOD; } return res; }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; if(!(cin>>T)) return 0;
    while(T--){
        int n; cin>>n;
        vector<long long> a(n);
        for(int i=0;i<n;i++) cin>>a[i];

        // 值压缩
        vector<long long> xs=a; sort(xs.begin(), xs.end());
        xs.erase(unique(xs.begin(), xs.end()), xs.end());
        int m = (int)xs.size();
        vector<int> A(n);
        for(int i=0;i<n;i++){
            int r = lower_bound(xs.begin(), xs.end(), a[i]) - xs.begin();
            A[i] = r+1; // 1-based
        }

        // L[i]
        vector<int> L(n);
        BITMax bit(m);
        for(int i=0;i<n;i++){
            L[i] = bit.query(A[i]-1) + 1;
            bit.update(A[i], L[i]);
        }

        // R[i]
        vector<int> R(n);
        bit.init(m);
        for(int i=n-1;i>=0;i--){
            int rev = m - A[i];
            int best = bit.query(rev);
            R[i] = best + 1;
            bit.update(m - A[i] + 1, R[i]);
        }

        int Lstar = *max_element(L.begin(), L.end());

        // 只保留在某条 LIS 上的位置
        vector<vector<int>> layerPos(Lstar+1);
        for(int i=0;i<n;i++) if (L[i]+R[i]-1==Lstar) layerPos[L[i]].push_back(i);

        // 每层：值去重并记录 (minPos, maxPos)
        vector<unordered_map<int, pair<int,int>>> layerVals(Lstar+1);
        for(int lev=1; lev<=Lstar; ++lev){
            unordered_map<int, pair<int,int>> mp;
            mp.reserve(layerPos[lev].size()*2+3);
            for(int idx: layerPos[lev]){
                int v = A[idx];
                int pos = idx+1;
                auto it = mp.find(v);
                if (it==mp.end()) mp.emplace(v, make_pair(pos,pos));
                else {
                    it->second.first = min(it->second.first, pos);
                    it->second.second = max(it->second.second, pos);
                }
            }
            layerVals[lev]=move(mp);
        }

        // 第1层
        unordered_map<int,int> dpPrev;
        for(auto &kv: layerVals[1]) dpPrev[kv.first]=1;

        // 层间 DP：二维离线（minPos 阈值 + 值的前缀和）
        for(int lev=2; lev<=Lstar; ++lev){
            vector<tuple<int,int,int>> prevItems; // (minPos, value, ways)
            prevItems.reserve(layerVals[lev-1].size());
            for(auto &kv: layerVals[lev-1]){
                int u = kv.first;
                int mn = kv.second.first;
                int ways = dpPrev.count(u)? dpPrev[u] : 0;
                prevItems.emplace_back(mn, u, ways);
            }
            sort(prevItems.begin(), prevItems.end(),
                 [](auto &x, auto &y){ return get<0>(x) < get<0>(y); });

            vector<pair<int,int>> curItems; // (threshold=maxPos-1, value)
            curItems.reserve(layerVals[lev].size());
            for(auto &kv: layerVals[lev]){
                int v = kv.first;
                int mx = kv.second.second;
                curItems.emplace_back(mx-1, v);
            }
            sort(curItems.begin(), curItems.end());

            BITSum bitSum(m);
            unordered_map<int,int> dpCur;
            int j=0;
            for(auto &q: curItems){
                int thr = q.first, v = q.second;
                while(j<(int)prevItems.size() && get<0>(prevItems[j]) <= thr){
                    int u = get<1>(prevItems[j]);
                    int ways = get<2>(prevItems[j]);
                    if (ways) bitSum.add(u, ways);
                    ++j;
                }
                // 只统计 u < v
                int waysV = bitSum.sum(v-1);
                dpCur[v] = waysV;
            }
            dpPrev.swap(dpCur);
        }

        int ans = 0;
        for(auto &kv: dpPrev){ ans += kv.second; if(ans>=MOD) ans-=MOD; }
        cout << (ans%MOD) << "\n";
    }
    return 0;
}

题目内容

给定一个长度为$n$的数组$a$，请你计算其中所有本质不同最长上升子序列的数量。由于答案可能非常大，请将结果对$998244353$取模后输出。

**[子序列]**如果一个序列可以通过删除原序列的若干(可能为零)元素得到，则称前者为后者的一个子序列。

**[上升序列]**我们称$s$为一个上升序列，当且仅当其中任意相邻元素满足$s_i<s_{i+1}$

**[本质不同序列]**若两个序列的长度不同，或在某一位置上的元素不同，则认为它们是不同的序列。

输入描述

每个测试文件均包含多组测试数据。

第一行输入一个整数$T(1≤T≤10^4)$代表数据组数，每组测试数据描述如下:

第一行输入一个正整数$n(1≤n≤2·10^5)$，代表数组$a$的长度。

第二行输入$n$个正整数$a_1,a_2,...,a_n (1≤a_i≤10^9),$代表$a$中的元素。

除此之外，保证单个测试文件的n之和不超过$2×10^5$。

输出描述

对于每组测试数据，输出一行一个整数，代表数组$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$}