自动搬运

查看原文

来自洛谷，原作者为

	Elma_ blog：https://www.cnblogs.com/came11ia

搬运于2025-08-24 22:34:48，当前版本为作者最后更新于2021-11-27 15:43:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一个显然的结论：对于原序列中的两个位置 $i,j(i < j)$，如果存在某一个最终得到的序列使得 $i,j$ 相邻，那么一定有 $\min\{a_{i+1},\cdots,a_{j-1}\} > \min\{a_i,a_j\}$，否则没有办法删过去。

据此我们可以设计 dp，设 $f_i$ 为以 $i$ 为结尾的最后可能得到的序列的总数，枚举上一个位置 $j$ 进行转移即可，其中 $j$ 需要满足上面给的那个条件，最后对所有可能作为结尾的位置统计答案。然而这样是 $O(n^2)$ 的，考虑进行优化。

对于一个位置 $i$，我们可以利用单调栈 $O(n)$ 求出用它左右两边最远可以删到哪里（实际上就是求左右两边第一个小于 $a_i$ 的数的位置），这样每个数就对应了一个区间 $[l_i,r_i]$。于是我们会发现上面那个条件就变成了区间 $[l_i,r_i]$ 和 $[l_j,r_j]$ 有交（因为每个数要么被 $i$ 删掉，要么被 $j$ 删掉）。

树状数组优化 dp 即可。时间复杂度 $O(n\log n)$，常数极小。

const int MN = 3e5 + 5, Inf = 1e9, Mod = 1e9 + 7;

int N, A[MN], f[MN], L[MN], R[MN], Ans, st[MN], tp;

struct BIT {
    int tr[MN];
    inline int lowbit(int x) {
        return x & (-x);
    }
    inline void Modify(int x, int k) {
        for (int i = x; i <= N; i += lowbit(i)) {
            tr[i] = (tr[i] + k) % Mod;
        }
    } 
    inline int Query(int x) {
        int res = 0;
        for (int i = x; i; i -= lowbit(i)) {
            res = (res + tr[i]) % Mod;
        }
        return res;
    }
} T;

signed main(void) {
    N = read();
    for (int i = 1; i <= N; i++) A[i] = read();
    for (int i = 1; i <= N + 1; i++) {
        while (tp && A[st[tp]] > A[i]) R[st[tp--]] = i - 1;
        st[++tp] = i;
    }
    for (int i = N; i >= 0; i--) {
        while (tp && A[st[tp]] > A[i]) L[st[tp--]] = i + 1;
        st[++tp] = i;
    }
    T.Modify(1, 1);
    for (int i = 1; i <= N; i++) {
        f[i] = (T.Query(N) - T.Query(L[i] - 1) % Mod + Mod) % Mod;
        T.Modify(R[i], f[i]);
    }
    int mn = Inf;
    for (int i = N; i >= 1; i--) {
        mn = min(mn, A[i]), Ans = (Ans + (mn == A[i] ? 1 : 0) * f[i]) % Mod;
    }
    printf("%lld\n", Ans);
    return 0;
}