题目解法：贪心分解 + 树状数组优化

问题分析

给定一个 $1 \sim n$ 的排列 $p$，要求找出尽可能多的不相交的上升子序列，且每个子序列的长度都等于最长上升子序列(LIS)的长度。

算法思路

核心思想

1. 计算LIS长度：使用树状数组优化计算每个位置结尾的LIS长度

2. 贪心分解：从最长的LIS开始，按层贪心选择字典序最小的路径

3. 维护候选集：为每个LIS长度维护候选位置，确保后续选择的可能性

算法步骤

步骤1：计算LIS

for (int i = 1; i <= n; i++) {
    f[i] = ask(a[i]) + 1;  // 树状数组查询
    add(a[i], f[i]);       // 树状数组更新
    mx = max(mx, f[i]);    // 记录最大LIS长度
}

步骤2：按层分组

for (int i = 1; i <= n; i++)
    E[f[i]].pb(i);  // E[k]存储所有LIS长度为k的位置

步骤3：贪心选择路径

对于每个候选的LIS：

• 从最高层(mx)开始，选择最靠右的位置

• 逐层向下，在满足上升条件的前提下选择最靠右的位置

• 如果无法形成完整路径，则终止选择

步骤4：维护候选集 在选择一条路径后，清理无效候选：

• 移除已使用的位置

• 移除无法形成新路径的位置

复杂度分析

时间复杂度：$O(n \log n + k \cdot n)$

• LIS计算：$O(n \log n)$

• 路径选择：最坏 $O(k \cdot n)$，其中 $k$ 是找到的LIS数量

空间复杂度：$O(n)$

• 存储LIS长度：$O(n)$

• 分层存储位置：$O(n)$

• 路径链接：$O(n)$

AC 代码实现

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N = 1e6 + 5;
int n, a[N], f[N], c[N], nxt[N], mx, pos[N], del[N];
vector<int> ans, E[N];

// 树状数组查询：求前缀最大值
int ask(int x) {
    int rec = 0;
    for (; x; x -= x & -x)
        rec = max(rec, c[x]);
    return rec;
}

// 树状数组更新：单点更新最大值
void add(int x, int w) {
    for (; x <= n; x += x & -x)
        c[x] = max(c[x], w);
}

int main() {
    scanf("%d", &n);
    
    // 步骤1：计算每个位置结尾的LIS长度
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        f[i] = ask(a[i]) + 1;
        add(a[i], f[i]);
        mx = max(mx, f[i]);  // 记录全局最大LIS长度
    }
    
    // 特殊情况：所有元素都是LIS长度为1
    if (mx == 1) {
        printf("%d %d\n", n, mx);
        for (int i = 1; i <= n; i++)
            printf("%d\n", i);
        return 0;
    }
    
    // 步骤2：按LIS长度分组
    for (int i = 1; i <= n; i++)
        E[f[i]].pb(i);
    
    // 步骤3：贪心选择不相交的LIS
    while (true) {
        int flg = 1, p = E[mx].back(), la;
        
        // 从顶层到底层构建一条LIS路径
        for (int i = mx - 1; i >= 1; i--) {
            la = p;
            
            // 清理比当前层位置大的候选
            while (E[i].size() && E[i].back() > p)
                E[i].pop_back();
            
            // 检查是否能形成上升序列
            if (!E[i].size() || a[E[i].back()] > a[la]) {
                flg = 0;
                break;
            }
            
            p = E[i].back();
            nxt[p] = la;  // 记录路径关系
        }
        
        if (!flg) break;  // 无法形成新的LIS
        
        ans.pb(p);  // 记录这条LIS的起点
        
        // 步骤4：清理已使用的候选
        for (int i = 1; i <= mx; i++)
            E[i].pop_back();
        
        // 清理无效候选：确保后续选择的可能性
        for (int i = 2; i <= mx; i++) {
            while (E[i].size()) {
                int p = E[i].back();
                auto it = lower_bound(E[i - 1].begin(), E[i - 1].end(), p);
                
                // 检查是否能形成新的路径
                if (it == E[i - 1].begin() || a[*prev(it)] > a[p])
                    E[i].pop_back();
                else
                    break;
            }
        }
    }
    
    // 输出结果
    printf("%d %d\n", (int)ans.size(), mx);
    for (int p : ans) {
        // 根据nxt数组重建完整路径
        for (int x = p; x; x = nxt[x])
            printf("%d ", x);
        puts("");
    }
    return 0;
}