题解 P7972 【[KSN2021] Self Permutation】

Elma_ · 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;
}