跳转至

250922&29 模拟赛 T4

250929 模拟赛 T4

给你一个长为 \(n\) 的排列 \(a_{1\sim n}\)，请你将它划分成两个子序列（不交且并为全集），使得第一个子序列 \(b\) 的上升链长度 \(x\)，和第二个子序列 \(c\) 的下降链长度 \(y\) 之和 \(x+y\) 最大。

一个序列的上升链长度定义为：从左边第一个元素开始，每次找到右边第一个更大的元素，然后跳过去，形成一条链；下降链同理。

\(n\le 2\times 10^5\)

考虑朴素 dp，设 \(f_{i,a,b}\) 表示考虑原排列的前 \(i\) 个数，上升链的最后一位是 \(a\)，下降链的最后一位是 \(b\)（也就是两个序列的 \(\max\) 和 \(\min\)），总长度的最大值。枚举当前数字给上升链还是下降链，容易做到 \(O(n^3)\)。

发现 \(a>b\) 时，介于 \([b,a]\) 之间的值不会有贡献；将大于 \(a\) 的数字放到下降链序列中，即可不产生贡献，小于 \(b\) 的数字放到上升链序列中也同理。因此其答案等于后缀中以 \(a,b\) 开头的 LIS 和 LDS 长度之和，而且显然是上界。

发现 \(a<b\) 时，每插入一个新元素，要么转化成 \(a>b\) 的情况，要么 \(a,b\) 不变，要么变为 \(a,x\) 或 \(x,b\)（\(a<x<b\)）。因此 \(a<b\) 时，\(a,b\) 一定是前缀值域中相邻的两项，也即本质不同的 \((a,b)\) 状态只有 \(O(n)\) 种。考虑用线段树优化，动态维护 \(a<b\) 情况中 \(f_{i,a}\) 的值，发现插入一个元素只直接改变 \(O(1)\) 个状态，因此容易维护。

考虑如何处理 \(a<b\) 变为 \(a>b\) 然后直接统计答案的贡献。我们需要动态维护从某个点开始的后缀 LIS 和 LDS。可以倒着扫一遍，考虑“二分法求 LIS 和 LDS”中记录的：长度为 \(i\) 的 LIS 和 LDS 的开头最大/最小是多少，查询以一个数开头的 LIS 或者 LDS 就是在这个数组中 lower_bound。发现插入一个数字只会对一段区间 \(+1\)，因此是好做的。

代码 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;

struct Range {
    int l, r;
} olis[N], olds[N];

int n, ans;
int a[N];

int lis[N], lds[N], li, ld;
int len_i[N], len_d[N];

namespace SegT1 {
    int mx[4 * N], tag[4 * N];
    inline int lc(int x) { return x << 1; }
    inline int rc(int x) { return x << 1 | 1; }
    inline void push_up(int p) { mx[p] = max(mx[lc(p)], mx[rc(p)]); }
    inline void spread(int p, int tg) { tag[p] += tg; mx[p] += tg; }
    inline void push_down(int p) { if(tag[p]) spread(lc(p), tag[p]), spread(rc(p), tag[p]), tag[p] = 0; }
    void add(int p, int l, int r, int ql, int qr, int v) {
        if(ql <= l && r <= qr) { spread(p, v); return; }
        int mid = (l + r) >> 1; push_down(p);
        if(ql <= mid) add(lc(p), l, mid, ql, qr, v);
        if(mid < qr) add(rc(p), mid + 1, r, ql, qr, v);
        push_up(p);
    }
    int query(int p, int l, int r, int ql, int qr) {
        if(ql > qr) return -INF;
        if(ql <= l && r <= qr) return mx[p];
        int mid = (l + r) >> 1, res = 0; push_down(p);
        if(ql <= mid) res = query(lc(p), l, mid, ql, qr);
        if(mid < qr) res = max(res, query(rc(p), mid + 1, r, ql, qr));
        return res;
    }
}

namespace SegT2 {
    int mx[4 * N], tag[4 * N];
    inline int lc(int x) { return x << 1; }
    inline int rc(int x) { return x << 1 | 1; }
    inline void push_up(int p) { mx[p] = max(mx[lc(p)], mx[rc(p)]); }
    inline void spread(int p, int tg) { tag[p] += tg; mx[p] += tg; }
    inline void push_down(int p) { if(tag[p]) spread(lc(p), tag[p]), spread(rc(p), tag[p]), tag[p] = 0; }
    void add(int p, int l, int r, int ql, int qr, int v) {
        if(ql <= l && r <= qr) { spread(p, v); return; }
        int mid = (l + r) >> 1; push_down(p);
        if(ql <= mid) add(lc(p), l, mid, ql, qr, v);
        if(mid < qr) add(rc(p), mid + 1, r, ql, qr, v);
        push_up(p);
    }
    int query(int p, int l, int r, int ql, int qr) {
        if(ql > qr) return -INF;
        if(ql <= l && r <= qr) return mx[p];
        int mid = (l + r) >> 1, res = 0; push_down(p);
        if(ql <= mid) res = query(lc(p), l, mid, ql, qr);
        if(mid < qr) res = max(res, query(rc(p), mid + 1, r, ql, qr));
        return res;
    }
}

set<int> st;

int main() {

    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];

    for(int i = 1; i <= n + 1; i++) lds[i] = n + 1;
    for(int i = n; i >= 1; i--) {
        int p = lower_bound(lds + 1, lds + 1 + ld, a[i]) - lds;
        olds[i] = (Range){a[i], lds[p] - 1};
        lds[p] = a[i]; ld = max(ld, p);
        len_d[i] = p;
    }
    for(int i = n; i >= 1; i--) {
        int p = upper_bound(lis + 1, lis + 1 + li, a[i], [](int a, int b) { return a > b; } ) - lis;
        olis[i] = (Range){lis[p] + 1, a[i]};
        lis[p] = a[i]; li = max(li, p);
        len_i[i] = p;
    }

    for(int i = 1; i <= n; i++) SegT1::add(1, 0, n, olds[i].l, olds[i].r, 1);
    for(int i = 1; i <= n; i++) SegT2::add(1, 0, n, olis[i].l, olis[i].r, 1);

    st.insert(0);
    st.insert(n + 1);
    for(int i = 1; i <= n; i++) {
        int pre = *--st.lower_bound(a[i]);
        int nxt = *st.upper_bound(a[i]);
        st.insert(a[i]);
        SegT1::add(1, 0, n, pre, nxt - 1, 1);
        SegT2::add(1, 0, n, pre, nxt - 1, 1);
        SegT1::add(1, 0, n, olds[i].l, olds[i].r, -1);
        SegT2::add(1, 0, n, olis[i].l, olis[i].r, -1);
        ans = max(ans, SegT1::query(1, 0, n, 0, pre - 1) + len_i[i]);
        ans = max(ans, SegT2::query(1, 0, n, nxt, n) + len_d[i]);
    }

    cout << ans << endl;

    return 0;
}