DDOSvoid's Blog

hdu 5306 Gorgeous Sequence

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

题目描述

http://acm.hdu.edu.cn/showproblem.php?pid=5306

简要题意：给定一个长度为 $n$ 的序列 $a_i$，现在有 $m$ 次操作，操作有三种，第一种操作给定 $l,r,v$，将区间 $[l,r]$ 中的所有数都变成 $min(a_i,v)$，第二种操作给定 $l,r$，求 $max(a_i),i\in[l,r]$，第三种操作给定 $l,r$，求 $[l,r]$ 的区间和

$n,m\le 10^6$

Solution

我们考虑维护用线段树区间最大值 $mx$ 和区间严格次大值 $se$ 以及区间最大值的个数 $t$ 和区间和 $sum$，那么对于一次区间取 $min$ 操作，如果 $v>= mx$，那么可以直接忽略；如果 $se<v< mx$，那么我们可以直接更新 $mx,sum$，然后我们将这个东西当成标记，具体实现中，我们直接将 $mx$ 当做标记即可，经过简单分类讨论，能够发现这个标记可以正常下传

如果 $se \ge v$，那么我们直接暴力 $dfs$，直到满足 $se <v<mx$，这样看似是暴力，实际上我们可以证明它的复杂度为 $O(n\log n)$，这里我们不沿用吉老师在论文中使用的标记类方法，我们定义一个节点的势能为它所管辖的区间中不同数的个数，整颗线段树的势能定义为所有节点的势能的和，上界为 $O(n\log n)$，注意到每暴力 $dfs$ 到一个点，这个点的次大值和最大值会被合并，也就是说值域减少 $1$，即势能减少 $1$

时间复杂度 $O((n+m)\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
#include <iostream>
#define maxn 1000010
#define ll long long
using namespace std;

int n, m, a[maxn];

#define lc i << 1
#define rc i << 1 | 1
struct Seg {
    int mx, se, t; ll v;
} T[maxn * 4];
inline void maintain(int i) {
    T[i] = T[lc];
    if (T[rc].mx > T[i].mx) T[i] = T[rc], T[i].se = max(T[lc].mx, T[rc].se); 
    else if (T[rc].mx == T[i].mx) T[i].t += T[rc].t, T[i].se = max(T[lc].se, T[rc].se);
    else T[i].se = max(T[lc].se, T[rc].mx);
    T[i].v = T[lc].v + T[rc].v;
}

void build(int i, int l, int r) {
    if (l == r) return T[i] = { a[l], -1, 1, a[l] }, void();
    int m = l + r >> 1;
    build(lc, l, m); build(rc, m + 1, r);
    maintain(i);
}

inline void Update(int i, int v) {
    T[i].v -= 1ll * T[i].t * (T[i].mx - v);
    T[i].mx = v; 
}

inline void pushdown(int i) {
    if (T[lc].mx > T[i].mx) Update(lc, T[i].mx);
    if (T[rc].mx > T[i].mx) Update(rc, T[i].mx);
}

void update(int i, int l, int r, int L, int R, int v) {
    if (l > R || r < L || T[i].mx <= v) return ;
    if (L <= l && r <= R && v > T[i].se) return Update(i, v); 
    int m = l + r >> 1; pushdown(i);
    update(lc, l, m, L, R, v); update(rc, m + 1, r, L, R, v);
    maintain(i);
}

int query_mx(int i, int l, int r, int L, int R) {
    if (l > R || r < L) return 0;
    if (L <= l && r <= R) return T[i].mx;
    int m = l + r >> 1; pushdown(i);
    return max(query_mx(lc, l, m, L, R), query_mx(rc, m + 1, r, L, R));
}

ll query_v(int i, int l, int r, int L, int R) {
    if (l > R || r < L) return 0;
    if (L <= l && r <= R) return T[i].v;
    int m = l + r >> 1; pushdown(i);
    return query_v(lc, l, m, L, R) + query_v(rc, m + 1, r, L, R);
}

inline void solve_0() {
    int x, y, z; cin >> x >> y >> z;
    update(1, 1, n, x, y, z); 
} 

inline void solve_1() {
    int x, y; cin >> x >> y;
    cout << query_mx(1, 1, n, x, y) << "\n";
}

inline void solve_2() {
    int x, y; cin >> x >> y;
    cout << query_v(1, 1, n, x, y) << "\n";
}

void work() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    build(1, 1, n); 
    for (int i = 1; i <= m; ++i) {
        int opt; cin >> opt;
        switch (opt) {
        case 0 : solve_0(); break; 
        case 1 : solve_1(); break;
        case 2 : solve_2(); break;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    
    int T; cin >> T;
    while (T--) work(); 
    return 0;
}