「CF2234E」Vlad, Misha and Two Arrays

发表于 分类于 本文字数： 995 阅读时长 ≈ 1 分钟

Description

Link：CF2234E

对于一个长度为 nn 的排列 pp，记 aia_i 表示有多少个区间 [l,r][l, r] (1≤l≤r≤n1 \leq l \leq r \leq n) 满足 pl,…,prp_l, \dots, p_r 中的最小值为 pip_i。

现给出 a1,…,ana_1, \dots, a_n，求出有多少个可能的排列 pp。

数据范围：1≤n≤5×1051 \leq n \leq 5\times 10^5，1≤ai≤10121 \leq a_i \leq 10^{12}。

时空限制：22s / 256256MiB。

Solution

一个比较歪的方向：根据 aa 数组算出每个数左边和右边第一个比它小的数 …

关注一下最小值 11：假设 11 在位置 ii，那么必有 ai=i(n−i+1)a_i = i(n - i + 1)。注意到 11 将区间分成了独立的左右两部分，因为跨过位置 ii 的区间，最小值必定是 11。先选出一部分的数分给左边，另一部分分给右边，此时的划分方案数为 (n−1i−1)\binom{n - 1}{i - 1}。

于是考虑分治。设 f(l,r)f(l, r) 表示 al,…,ara_l, \dots, a_r 能复原多少个关于 r−l+1r - l + 1 的排列。先找到最小值的位置 pp，满足 ap=(p−l+1)(r−p+1)a_p = (p - l + 1)(r - p + 1)，然后再将剩余的数划分给左右两部分，于是有

f(l,r)=f(l,p−1)×f(p+1,r)×(r−lp−l)f(l, r) = f(l, p - 1)\times f(p + 1, r)\times \binom{r - l}{p - l}

但是寻找 pp 的过程，不能正着扫一遍或者反着扫一遍，否则都会被构造数据卡成 O(n2)\mathcal{O}(n^2)。

每次从左侧取一个数判断，再从右侧取一个数判断。如此往复直到找到满足条件的 pp 为止。容易发现枚举 pp 的开销，取决于较小区间的长度。本质上是一个启发式分裂。

时间复杂度 O(nlog⁡n)\mathcal{O}(n \log n)。

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
108
109
110
111
112
113
#include <bits/stdc++.h>

using i64 = long long;

#define debug(a) std::cout << #a << '=' << (a) << ' '

template <class T>
inline void chmin(T &x, const T &y) {
    if (x > y) {
        x = y;
    }
}
template <class T>
inline void chmax(T &x, const T &y) {
    if (x < y) {
        x = y;
    }
}

const int mod = 1e9 + 7;

template <class T>
inline int qpow(int a, T b, int p) {
    int ans = 1;
    for (; b; b >>= 1) {
        if (b & 1) ans = 1ll * ans * a % p;
        a = 1ll * a * a % p;
    }
    return ans;
}

struct BinomCoef {
    std::vector<int> fact, facv;

    BinomCoef() {}
    BinomCoef(int n) {
        init(n);
    }

    void init(int n) {
        fact.resize(n + 1), facv.resize(n + 1);
        fact[0] = 1;
        for (int i = 1; i <= n; i ++) {
            fact[i] = 1ll * fact[i - 1] * i % mod;
        }
        facv[n] = qpow(fact[n], mod - 2, mod);
        for (int i = n - 1; i >= 0; i --) {
            facv[i] = 1ll * facv[i + 1] * (i + 1) % mod;
        }
    }

    int binom(int n, int m) {
        if (n < m || m < 0) {
            return 0;
        }
        return 1ll * facv[m] * facv[n - m] % mod * fact[n] % mod;
    }
} bc(500000);

const int N = 500100;

int n;
i64 a[N];

int solve(int l, int r) {
    if (l > r) {
        return 1;
    }
    auto check = [&] (int i) {
        return a[i] == 1ll * (i - l + 1) * (r - i + 1);
    };

    int i = l, j = r;
    while (i <= j) {
        if (i <= j) {
            if (check(i)) {
                return 1ll * solve(l, i - 1) * solve(i + 1, r) % mod * bc.binom(r - l, i - l) % mod;
            }
            i ++;
        }
        if (i <= j) {
            if (check(j)) {
                return 1ll * solve(l, j - 1) * solve(j + 1, r) % mod * bc.binom(r - l, j - l) % mod;
            }
            j --;
        }
    }
    return 0;
}

void work() {
    std::cin >> n;

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

    std::cout << solve(1, n) << '\n';
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);

    int T;
    std::cin >> T;

    while (T --) {
        work();
    }

    return 0;
}