[CF1468A] LaIS - dp,树状数组

Description

给出一个长度为 \(n\) 的序列 \(a_1,a_2,...,a_n\) ，请找出一个子序列 \(b_1,b_2,...,b_k\) ，使其满足 \(\min(b_1,b_2)\le \min(b_2,b_3)\le ...\le \min(b_{k-1},b_k)\) ，求出 \(k\) 的最大值。

Solution

LaIS 中由一个子序列满足是 IS 并且元素距离不超过 2，称为这个 LaIS 的核

我们考虑对着这个核去 dp

我们按值升序扫描所有元素，设 \(f[i]\) 表示以 \(a[i]\) 为核的结尾的 LaIS 的最大长度

假如现在扫描的是 i，我们需要考虑

• 以 \(a[i]\) 作为 LaIS 的结尾，并且上一个元素也是核，此时 \(f[i]\) 答案更新为 \(f[1..i-1]\) 中的 max + 1
• 以 \(a[i]\) 作为 LaIS 的结尾，并且上一个元素不是核，此时我们需要找到 i 之前第一个大于等于 \(a[i]\) 的元素，因为它大于当前扫描值，我们把它作为非核元素，再查询他前面的所有核结尾的最大值，进行转移，因此此时 \(f[i]\) 更新为 \(f[1..pos-1]\) 中的 max + 2

单点修改，前缀查询，用一个树状数组（线段树当然也行）维护即可

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

#define int long long

struct BITree
{
    int n;
    vector<int> a;

    BITree(int n) : n(n)
    {
        a.resize(n + 2);
    }

    int lowbit(int p)
    {
        return p & (-p);
    }

    void Update(int p, int val)
    {
        while (p <= n)
        {
            a[p] = max(a[p], val);
            p += lowbit(p);
        }
    }

    int Max(int p)
    {
        int ans = 0;
        while (p > 0)
        {
            ans = max(ans, a[p]);
            p -= lowbit(p);
        }
        return ans;
    }
};

void GetNext(int n, const vector<int> &a, vector<int> &nxt)
{
    stack<int> sta;
    for (int i = n; i >= 1; i--)
    {
        while (sta.size() && a[i] >= a[sta.top()])
        {
            nxt[sta.top()] = i;
            sta.pop();
        }
        sta.push(i);
    }
}

void solve()
{
    int n;
    cin >> n;

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

    vector<int> nxt(n + 2);
    GetNext(n, a, nxt);

    vector<pair<int, int>> seq;
    for (int i = 1; i <= n; i++)
        seq.push_back({a[i], i});

    sort(seq.begin(), seq.end());

    BITree bitree(n);

    for (int _ = 0; _ < n; _++)
    {
        int i = seq[_].second;
        int res = bitree.Max(i - 1) + 1;
        if (nxt[i])
        {
            res = max(res, bitree.Max(nxt[i] - 1) + 2);
        }
        bitree.Update(i, res);
    }

    cout << bitree.Max(n) << endl;
}

signed main()
{
    ios::sync_with_stdio(false);

    int t;
    cin >> t;
    while (t--)
        solve();
}