题目描述

难度分:$2200$

输入$n(1 \leq n \leq 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq 10^5)$。

定义$LIS$为$a$的最长严格递增子序列，注意可能有多个$LIS$。对于每个$i$：

• 如果$a[i]$不在任何$LIS$中，输出$1$。
• 如果$a[i]$在至少一个$LIS$中，但不在所有$LIS$中，输出$2$。
• 如果$a[i]$在所有$LIS$中，输出$3$。

输出在同一行，不要加空格。

注意，$a=[1,2,2,3]$有两个相同的$LIS$ $[1,2,3]$，其中$1$和$3$都在这两个$LIS$中，但$2$ 只在其中一个$LIS$不在另一个$LIS$中，所以输出$3223$。

输入样例$1$

1
4

输出样例$1$

3

输入样例$2$

4
1 3 2 5

输出样例$2$

3223

输入样例$3$

4
1 5 2 3

输出样例$3$

3133

算法

前后缀分解+动态规划

状态定义

$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]$的值域比较小，不需要对数值进行离散化。

然后开始枚举$i \in [1,n]$，看每个$a[i]$属于哪种类型？可以发现，如果满足$f[i]+g[i]=maxlen+1$，那么$i$要么是$2$类型要么是$3$类型。否则就应该是$1$类型，它不属于任何一个$LIS$。重点是如何区分$2$和$3$两种类型，可以发现如果存在$i \neq j$满足$f[i]=f[j]$和$g[i]=g[j]$，那么$i$和$j$就都是$2$类型，因为无论是选$i$还是$j$都不影响最长上升子序列。所以用一个哈希表存储二元组$(f[i],g[i])$的频数，在$f[i]+g[i]=maxlen+1$的情况下，如果$(f[i],g[i])$出现次数超过$1$，$i$就是$2$类型，否则是$3$类型。

复杂度分析

时间复杂度

从前往后进行一次DP求$f$，再从后往前进行一次DP求$g$，时间复杂度为$O(nlog_2n)$。枚举$i \in [1,n]$，存储二元组$(f[i],g[i])$的频数，这里我用的有序表，时间复杂度为$O(nlog_2n)$，可以用哈希表降至$O(n)$，但是算法的瓶颈不在于次，这个优化意义不大。最后枚举$i \in [1,n]$，检查$f[i]+g[i]=maxlen+1$是否成立，并查表判断每个$i$的类型，时间复杂度为$O(n)$。

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

空间复杂度

空间瓶颈在于线段树和存储二元组$(f[i],g[i])$频数的哈希表空间，都是线性的。因此，整个算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> PII;

const int N = 100010;
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() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        f[i] = g[i] = 1;
    }
    SegmentTree seg;
    seg.build(1, 1, N);
    int maxlen = 1;
    for(int i = 1; i <= n; i++) {
        int prelen = seg.query(1, a[i] - 1).maximum;
        if(seg.query(a[i], a[i]).maximum < prelen + 1) {
            seg.modify(a[i], prelen + 1);
        }
        f[i] = prelen + 1;
        maxlen = max(maxlen, f[i]);
    }
    seg.build(1, 1, N);
    for(int i = n; i >= 1; i--) {
        int suflen = seg.query(a[i] + 1, N).maximum;
        if(seg.query(a[i], a[i]).maximum < suflen + 1) {
            seg.modify(a[i], suflen + 1);
        }
        g[i] = suflen + 1;
    }
    map<pair<int, int>, int> mp;
    for(int i = 1; i <= n; i++) {
        mp[{f[i], g[i]}]++;
    }
    for(int i = 1; i <= n; i++) {
        if(f[i] + g[i] == maxlen + 1) {
            if(mp[{f[i], g[i]}] > 1) {
                printf("%d", 2);
            }else {
                printf("%d", 3);
            }
        }else {
            printf("%d", 1);
        }
    }
    return 0;
}