Pedestrian1's BLOG
0%

AtCoder Regular Contest 115 E - LEQ and NEQ

发表于

题意：给定个数，求个数满足下列条件的方案数： 数据范围：

类似杭电多校1多项式题的容斥，但是此时由于的值是不固定的，所以只能写成形式，设为前i个序列的答案，枚举钦定最后个不合法，则有

单调栈求出作为最小值的左边界，从转移到时只会影响一段后缀，用线段树维护即可，时间复杂度也可以用笛卡尔树做到

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
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp>

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
typedef long long ll;
//tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> tr;
//__gnu_pbds::priority_queue<int, greater<int>, pairing_heap_tag> qu;
//typedef trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update> pref_trie;
const int N = 500005;
int n, m, k;
ll a[N];
int stk[N], L[N];
ll lazy[N << 2];
struct point
{
    ll sum, f;
} c[N << 2];
const ll mod = 998244353;

inline void pushup(int k)
{
    c[k].sum = (c[k << 1].sum + c[k << 1 | 1].sum) % mod;
    c[k].f = (c[k << 1].f + c[k << 1 | 1].f) % mod;
}

const ll inf = 1e9;

inline void pushdown(int k)
{
    if (lazy[k] != inf)
    {
        lazy[k << 1] = lazy[k << 1 | 1] = lazy[k];
        c[k << 1].sum = c[k << 1].f * lazy[k] % mod;
        c[k << 1 | 1].sum = c[k << 1 | 1].f * lazy[k] % mod;
        lazy[k] = inf;
    }
}

void update(int L, int R, int l, int r, int k, ll v)
{
    if (L <= l && r <= R)
    {
        c[k].sum = v * c[k].f % mod;
        lazy[k] = v;
        return;
    }
    int m = (l + r) >> 1;
    pushdown(k);
    if (L <= m)update(L, R, l, m, k << 1, v);
    if (R > m)update(L, R, m + 1, r, k << 1 | 1, v);
    pushup(k);
}

void insert(int l, int r, int k, int x, ll v, ll f)
{
    if (l == r)
    {
        c[k] = {v * f % mod, f};
        return;
    }
    int m = (l + r) >> 1;
    pushdown(k);
    if (x <= m)insert(l, m, k << 1, x, v, f);
    else insert(m + 1, r, k << 1 | 1, x, v, f);
    pushup(k);
}

int main()
{
    int p, q, u, v, w, x, y, z, T;
    cin >> n;
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    fill(lazy, lazy + n * 4, inf);
    int top = 0;
    for (int i = n; i; i--)
    {
        while (top && a[stk[top]] >= a[i])
            L[stk[top--]] = i;
        stk[++top] = i;
    }
    insert(0, n, 1, 0, 1, 1);
    for (int i = 1; i <= n; i++)
    {
        update(L[i], i - 1, 0, n, 1, mod - a[i] % mod);
        if (i == n)cout << (i & 1 ? mod - 1 : 1) * c[1].sum % mod;
        insert(0, n, 1, i, a[i], c[1].sum);
    }
    return 0;
}