跃迁引擎启动

HDu5306 Gorgeous Sequence 题解

发表于 更新于 分类于 ， 阅读次数：

对于一类区间最值更新问题，我们可以维护最大值，最大值个数和次大值。

对于最小值更新 x：

  1. $max[l \dots r] \le x$ ：无需更新
  2. $ secondMax[l \dots r] < x < max[l \dots r]$ ：将 $max[l \dots r]$ 覆盖为 x，打标记。
  3. $secondMax[l \dots r] \ge x$：暴力递归。

参考2016年IOI国家队论文，可以证明以上算法均摊时间复杂度 $O(q \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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ms(a,b) memset(a,b,sizeof(a))
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
using namespace std;
typedef long long ll;
const int maxn = 1000000 + 5;

int n, m, a[maxn], mx[maxn << 2], cnt[maxn << 2], se[maxn << 2], add[maxn << 2];
ll sum[maxn << 2];

void pushup(int rt){
    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
    if (mx[rt << 1] == mx[rt << 1 | 1]){
        se[rt] = max(se[rt << 1], se[rt << 1 | 1]);
        mx[rt] = mx[rt << 1];
        cnt[rt] = cnt[rt << 1] + cnt[rt << 1 | 1];
    }
    else if (mx[rt << 1] < mx[rt << 1 | 1]){
        se[rt] = max(mx[rt << 1], se[rt << 1 | 1]);
        mx[rt] = mx[rt << 1 | 1];
        cnt[rt] = cnt[rt << 1 | 1];
    }
    else {
        se[rt] = max(mx[rt << 1 | 1], se[rt << 1]);
        mx[rt] = mx[rt << 1];
        cnt[rt] = cnt[rt << 1];
    }
}
void pushdown(int rt){
    if (add[rt] == -1) return;
    // 区间覆盖
    int& t = add[rt]; int ls = rt << 1, rs = rt << 1 | 1;
    if (mx[ls] > t && t > se[ls]) {
        sum[ls] -= 1ll * (mx[ls] - t) * cnt[ls];
        add[ls] = mx[ls] = t;
    }
    if (mx[rs] > t && t > se[rs]){
        sum[rs] -= 1ll * (mx[rs] - t) * cnt[rs];
        add[rs] = mx[rs] = t;
    }
    t = -1;
}
void build(int l, int r, int rt){
    add[rt] = -1; 
    if (l == r){
        se[rt] = -1; cnt[rt] = 1;
        sum[rt] = mx[rt] = a[l];
        return;
    }
    int m = l + r >> 1;
    build(lson); build(rson);
    pushup(rt);
}
void update(int L, int R, int t, int l, int r, int rt){
    if (mx[rt] <= t) return;
    if (L <= l && r <= R && se[rt] < t){
        sum[rt] -= 1ll * (mx[rt] - t) * cnt[rt];
        mx[rt] = add[rt] = t; 
        return;
    }
    int m = l + r >> 1; 
    pushdown(rt);
    if (L <= m) update(L, R, t, lson);
    if (R > m) update(L, R, t, rson);
    pushup(rt);
}
int qmax(int L, int R, int l, int r, int rt){
    if (L <= l && r <= R) return mx[rt];
    int m = l + r >> 1; int ans = 0;
    pushdown(rt);
    if (L <= m) ans = max(ans, qmax(L, R, lson));
    if (R > m) ans = max(ans, qmax(L, R, rson));
    return ans;
}
ll qsum(int L, int R, int l, int r, int rt){
    if (L <= l && r <= R) return sum[rt];
    int m = l + r >> 1; ll ans = 0;
    pushdown(rt);
    if (L <= m) ans += qsum(L, R, lson);
    if (R > m) ans += qsum(L, R, rson);
    return ans;
}

int main(){
    int T; scanf("%d", &T);
    while (T--){
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) scanf("%d", a + i);
        build(1, n, 1); int op, x, y, t;
        while (m--){
            scanf("%d", &op);
            if (op == 0){
                scanf("%d%d%d", &x, &y, &t);
                update(x, y, t, 1, n, 1);
            }
            if (op == 1){
                scanf("%d%d", &x, &y);
                printf("%d\n", qmax(x, y, 1, n, 1));
            }
            if (op == 2){
                scanf("%d%d", &x, &y);
                printf("%lld\n", qsum(x, y, 1, n, 1));
            }
        }
    }    
    return 0;
}