DDOSvoid's Blog

Luogu P6655 [YsOI2020]制高

发表于 分类于
本文字数： 1.9k 阅读时长 ≈ 2 分钟

题目描述

https://www.luogu.com.cn/problem/P6655

Solution

我们考虑 $dp$，令 $f[i]$ 表示 $i$ 为制高点的方案数

但我们发现这个东西并不好转移，原因在于后面的加边会影响 $f[i]$ 的大小

所以我们换一种定义，我们令 $f[i]$ 表示 $i$ 为制高点的概率

那么容易得到 $f_i=\frac{1}{r_i-l_i+1}\sum_{j=l_i}^{r_i}f_j\times [hi\ge h_j]$

最后答案为 $S\sum_{i=1}^nf_i$，其中 $S=\prod_{i=2}^nr_i-l_i+1$

这个东西显然可以用主席树做到 $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
#include <iostream>
#include <cstdio>
#include <algorithm>
#define maxn 100010
#define ll long long
using namespace std;

const int p = 998244353;

ll pow_mod(ll x, ll n) {
    ll s = 1;
    for (; n; n >>= 1) {
        if (n & 1) s = s * x % p;
        x = x * x % p;
    }
    return s; 
}

int n, a[maxn], l[maxn], r[maxn];

int b[maxn], cnt;
void init_hash() {
    for (int i = 1; i <= n; ++i) b[i] = a[i];
    sort(b + 1, b + n + 1); cnt = unique(b + 1, b + n + 1) - b - 1;
    for (int i = 1; i <= n; ++i) a[i] = lower_bound(b + 1, b + cnt + 1, a[i]) - b;
} 

#define lc T[i].ch[0]
#define rc T[i].ch[1]
#define Lc T[j].ch[0]
#define Rc T[j].ch[1]
struct zhuxi {
    int v, ch[2];
} T[maxn * 20]; int top, rt[maxn];
void update(int &i, int j, int l, int r, int k, int v) {
    i = ++top; T[i] = T[j]; T[i].v = (T[i].v + v) % p; 
    if (l == r) return ; int m = l + r >> 1; 
    if (k <= m) update(lc, Lc, l, m, k, v);
    else update(rc, Rc, m + 1, r, k, v); 
}

int query(int i, int j, int l, int r, int L, int R) {
    if (l > R || r < L) return 0;
    if (L <= l && r <= R) return (T[j].v - T[i].v) % p; 
    int m = l + r >> 1;
    return (query(lc, Lc, l, m, L, R) + query(rc, Rc, m + 1, r, L, R)) % p; 
}

int f[maxn];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr); 

    cin >> n; ll ans = 0, S = 1; 
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 2; i <= n; ++i) cin >> l[i] >> r[i];
    init_hash(); f[1] = 1; update(rt[1], rt[0], 1, cnt, a[1], f[1]); 
    for (int i = 2; i <= n; ++i) S = S * (r[i] - l[i] + 1) % p; ans = S; 
    for (int i = 2; i <= n; ++i) {
        f[i] = pow_mod(r[i] - l[i] + 1, p - 2) * query(rt[l[i] - 1], rt[r[i]], 1, cnt, 1, a[i]) % p;
        update(rt[i], rt[i - 1], 1, cnt, a[i], f[i]);
        ans = (ans + S * f[i]) % p; 
    } cout << (ans + p) % p << "\n";
    return 0;
}