2023牛客暑期多校训练营8

H - Insert 1, Insert 2, Insert 3, ...

https://ac.nowcoder.com/acm/contest/57362/H

题意

给定长度为 n 的序列 {a}i=1n，问有多少个连续子区间 [l,r] 满足这个子区间可以通过若干次依次按顺序插入 1,2,3⋯,k 的子序列构成。1≤n≤106，1≤ai≤n。

题解

思路

一个合法的区间一定以 1 开头，那么就可以考虑对于每个右端点 r，计算出有多少个左侧的 1 能和它组成合法区间，统计总数便是题目答案。

对于一个数 x，它必须与左侧的最近的一个还没有被匹配的 x−1 匹配，如果没有能匹配的则不合法。如：

1^,1¯,2¯,2^,3^,3¯,3

数字顶上标记相同的代表匹配为一组，可以看到最后一个 3 需要在左边找到一个 2 匹配，但是在左边的 2 已经全部被其他 3 匹配占用了，没有剩余的还没有被匹配的 2。因此这个 3 不合法，它的答案是 0.

如果匹配上了，那答案的数量如何计算。对于每个匹配的一组数，找到它们起点（也就是 1）和起点前面一共有几个 1，数量便是合法区间的数量了。如：

1,1¯,1^,2^,3^,2¯,3¯

对于第一个 3，它的起点是第三个 1，前面一共 3 个 1，因此答案是 3。对于第二个 3，它的起点是第二个 1，因此答案是 2。

不过有一个要点是，如果有一个不合法的数将序列分开，那么左边的 1 就不能再被匹配了，因为如果想要匹配左边的 1 必须跨过那个不合法的数，那这个区间肯定就不合法了。如：

1,1,1,1,1,99,1,2,3

对于最后一个 3，它的起点前面的 1 被 99 这个不合法的数挡住了，所以总共只有 1 个能够匹配。

维护方式

使用 106 个栈（用 vector 而不是 stack，要不然 MLE）维护每个数的位置，对于一个数 x，在第 x−1 个栈中找栈顶，如果是空栈则这个数不成立，如果找到栈中有数，则将其弹出，并在第 x 个栈中压入 x 的下标。如此就可以快速找到左侧的最近的一个还没有被匹配的 x−1 的位置。

对于 1 的个数的维护，使用单调栈完成。考虑到当从左到右考虑时，能匹配的 1 的位置从右往左移动，且是一个单调的。因此可以用单调栈弹掉不合法的 1，栈中剩下的数目便是答案数。对于碰见不合法的数，直接把栈弹空就行。

代码

#include <bits/stdc++.h>
#define endl '\n'
#define int long long

using namespace std;

constexpr int MAXN = 1e6 + 10;
vector<int> p[MAXN], s;

void solve()
{
    int n;
    cin >> n;
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        if (x == 1)
        {
            p[1].push_back(i);
            s.push_back(i);
            ans += s.size();
        }
        else if (p[x - 1].empty())
        {
            s.clear();
        }
        else
        {
            int y = p[x - 1].back();
            p[x - 1].pop_back();
            p[x].push_back(y);
            while (s.size() && s.back() > y)
                s.pop_back();
            ans += s.size();
        }
    }
    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}