题目描述

难度分:$1639$

输入测试用例数$T$，对于每个$case$，给定一个长度为$n$的数组$a$，求出所有$i$满足存在一个$a$的最长上升子序列是包括$i$的，先输出满足条件的索引数，再依次输出所有满足条件的$i$。

输入样例$1$

1
5
2 1 4 5 3

输出样例$1$

4
1 2 3 4

输入样例$2$

2
6
2 5 3 4 3 4
5
10000 1000 100 1 10

输出样例$2$

5
1 3 4 5 6
2
4 5

算法

前后缀分解+动态规划

状态定义

$f[i]$表示以$a[i]$结尾的最长上升子序列长度，$g[i]$表示以$a[i]$开头的最长上升子序列长度。这样一来，如果$i$属于某个最长上升子序列，一定满足$f[i]+g[i]=maxlen+1$，其中$maxlen$就是$a$的最长上升子序列长度，加$1$是因为$a[i]$算了两次。

状态转移

$f$和$g$的状态转移是类似的，由于$n \leq 2 \times 10^5$，所以需要用$O(nlog_2n)$的做法来求。利用树状数组或线段树来优化这个DP，对$a[i]$的数值开权值线段树$seg$，$seg[a[i]]$表示以数值$a[i]$结尾的最长上升子序列的最大长度。但考虑到$a[i] \leq 10^9$，需要对数值进行离散化。

复杂度分析

时间复杂度

对$a$数组中的元素进行离散化，需要先排序，然后双指针去重，时间复杂度的瓶颈在于排序，为$O(nlog_2n)$。之后从前往后进行一次DP求$f$，再从后往前进行一次DP求$g$，时间复杂度为$O(nlog_2n)$。最后枚举$i \in [1,n]$，检查$f[i]+g[i]=maxlen+1$是否成立，时间复杂度为$O(n)$。

综上，整个算法的时间复杂度为$O(nlog_2n)$。

空间复杂度

空间瓶颈在于线段树和离散化$a$数组中的值所消耗的数组空间和哈希表空间，都是线性的。因此，整个算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;

const int N = 200010;
int n, a[N], f[N], g[N];

class SegmentTree {
public:
    struct Info {
        int l, r, maximum;
        Info() {}
        Info(int left, int right, int val): l(left), r(right), maximum(val) {}
    } seg[N<<2];

    explicit SegmentTree() {}

    void build(int u, int l, int r) {
        if(l == r) {
            seg[u] = Info(l, r, 0);
        }else {
            int mid = l + r >> 1;
            build(u<<1, l, mid);
            build(u<<1|1, mid + 1, r);
            pushup(u);
        }
    }

    void modify(int pos, int val) {
        modify(1, pos, val);
    }

    Info query(int l, int r) {
        if(l > r) return Info(0, 0, 0);
        return query(1, l, r);
    }

private:
    void modify(int u, int pos, int val) {
        if(seg[u].l == pos && seg[u].r == pos) {
            seg[u] = Info(pos, pos, val);
        }else {
            int mid = seg[u].l + seg[u].r >> 1;
            if(pos <= mid) modify(u<<1, pos, val);
            else modify(u<<1|1, pos, val);
            pushup(u);
        }
    }

    Info query(int u, int l, int r) {
        if(l <= seg[u].l && seg[u].r <= r) return seg[u];
        int mid = seg[u].l + seg[u].r >> 1;
        if(r <= mid) {
            return query(u<<1, l, r);
        }else if(mid < l) {
            return query(u<<1|1, l, r);
        }else {
            return merge(query(u<<1, l, r), query(u<<1|1, l, r));
        }
    }

    void pushup(int u) {
        seg[u] = merge(seg[u<<1], seg[u<<1|1]);
    }

    Info merge(const Info& lchild, const Info& rchild) {
        Info info;
        info.l = lchild.l;
        info.r = rchild.r;
        info.maximum = max(lchild.maximum, rchild.maximum);
        return info;
    }
};

int main() {
    int t;
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        vector<int> vals;
        vals.push_back(0);
        vals.push_back((int)1e9 + 1);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            vals.push_back(a[i]);
            f[i] = g[i] = 1;
        }
        sort(vals.begin(), vals.end());
        vals.erase(unique(vals.begin(), vals.end()), vals.end());
        int sz = vals.size();
        unordered_map<int, int> val2pos;
        for(int i = 0; i < sz; i++) {
            val2pos[vals[i]] = i + 1;
        }
        SegmentTree seg;
        seg.build(1, 1, sz);
        int maxlen = 1;
        for(int i = 1; i <= n; i++) {
            int index = val2pos[a[i]];
            int prelen = seg.query(1, index - 1).maximum;
            if(seg.query(index, index).maximum < prelen + 1) {
                seg.modify(index, prelen + 1);
            }
            f[i] = prelen + 1;
            maxlen = max(maxlen, f[i]);
        }
        seg.build(1, 1, sz);
        for(int i = n; i >= 1; i--) {
            int index = val2pos[a[i]];
            int suflen = seg.query(index + 1, sz).maximum;
            if(seg.query(index, index).maximum < suflen + 1) {
                seg.modify(index, suflen + 1);
            }
            g[i] = suflen + 1;
        }
        vector<int> pos;
        for(int i = 1; i <= n; i++) {
            if(f[i] + g[i] == maxlen + 1) {
                pos.push_back(i);
            }
        }
        printf("%d\n", (int)pos.size());
        for(int x: pos) {
            printf("%d ", x);
        }
        puts("");
    }
    return 0;
}