cf1913D

分治+笛卡尔树

碎碎念

原题(codeforces)

赛时这题wa了。
赛后看到d题大多题解都是栈啊什么的，我没看懂，最终看到一个跟我思路完全相同的一个题解，检查发现没有特判如下的情况（其实是画蛇添足），魂都被气飞了。

1
2
1
1

新人第一发题解wa了，第二发求过（

题解

  • 首先观察整个数列 定义 是最小值的下标。显然你不能删除最小值，并且删除 左侧和 右侧的元素是独立事件。因此答案就是 和 答案的乘积。

  • 那么如何处理一般化的数列 呢？显然我们只有两种选择：保留 （ 中最小值的下标），或者使用 或 （如果它们存在）来删除 。

  • 定义 ， 分别是 和 的答案。不论何时，我们可以有 种方法来保留 。如果 , 我们有 种方法来删除 。如果 , 我们有 种方法来删除 。如果 且 , 我们重复计算了删除 中所有元素的情况，因此我们需要再减去 。

  • 原本我使用 min_element 求最小值，经群 u 提醒（指直接上手 hack ）构造单调序列可以 tle ，因此我们需要预处理一个笛卡尔树。

原文 by TheScrasse

  • Solve the problem for the whole array . Let the position of the minimum. Note that you cannot delete the minimum, and the moves on the left and on the right are independent. So the answer is the product of the answers on and .

  • How to solve for a generic interval ? Note that you can either keep (the position of the minimum value in ) “alive”, or use the elements in positions and (if they exist) to delete .

  • Let , be the answers in the intervals and . In any case, we can keep “alive” (in ways). If , we can delete (actually, all elements in ) in ways. If , we can delete (actually, all elements in ) in ways. If both and , we are overcounting the case where we remove every element in , so we must add back.

转载已征得作者同意。

代码

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
#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MAXN = 1e6;
constexpr int mod = 998244353;
int nums[MAXN], stk[MAXN], rs[MAXN], ls[MAXN], n, t, top;
using pt = pair<int, int>;

int sted(int l, int r, int i) {
    if (l > r || i == -1)return 1;
    //cout << i << endl;
    int lf = sted(l, i - 1, ls[i]) % mod;//左边1
    int rf = sted(i + 1, r, rs[i]) % mod;//右边2
    //if (i == 2)cout << rs[i] << endl;
    int ret = (lf * rf) % mod;
    if (l != 0)ret += rf;
    if (r != n - 1)ret += lf;
    if (l != 0 && r != n - 1)ret--;
    return ret;
}

void solve() {
    cin >> n;
    for (int i = 0;i < n;++i)cin >> nums[i];
    for (int i = 0;i < n;++i)rs[i] = -1;
    for (int i = 0;i < n;++i)ls[i] = -1;
    top = 0;
    for (int i = 0; i < n; i++) {
        int k = top;
        while (k > 0 && nums[stk[k - 1]] > nums[i]) k--;
        if (k) rs[stk[k - 1]] = i;  // rs代表笛卡尔树每个节点的右儿子
        if (k < top) ls[i] = stk[k];  // ls代表笛卡尔树每个节点的左儿子
        stk[k++] = i;
        top = k;
    }
    cout << sted(0, n - 1, stk[0]) % mod;
}

signed main() {
    ios::sync_with_stdio(false);
    cin >> t;
    while (t--) {
        solve();
        cout << '\n';
    }
    return 0;
}
//by Empty_Dust AC