HDU5306 Gorgeous Sequence

维护一个序列 $a$：

  1. 0 l r t $\forall l \le i \le r, a_i = min(a_i, t)$。
  2. 1 l r 输出区间 $[l, r]$ 中的最大值。
  3. 2 l r 输出区间 $[l, r]$ 和。
1
#include <iostream>
2
#include <cstdio>
3
#define ls (o << 1)
4
#define rs (o << 1 | 1)
5
using namespace std;
6
const int N = 1E6 + 7;
7
long long a[N];
8
struct SGT{
9
    long long mx, sec, sum, tag;
10
    int num;
11
}t[N << 2];
12
void pushup(int o){
13
    t[o].sum = t[ls].sum + t[rs].sum;
14
    if(t[ls].mx == t[rs].mx){
15
        t[o].mx = t[ls].mx;
16
        t[o].sec = max(t[ls].sec, t[rs].sec);
17
        t[o].num = t[ls].num + t[rs].num;
18
    }
19
    else if(t[ls].mx > t[rs].mx){
20
        t[o].mx = t[ls].mx;
21
        t[o].sec = max(t[ls].sec, t[rs].mx);
22
        t[o].num = t[ls].num;
23
    }
24
    else{
25
        t[o].mx = t[rs].mx;
26
        t[o].sec = max(t[rs].sec, t[ls].mx);
27
        t[o].num = t[rs].num;
28
    }
29
}
30
void change(int o, long long tag){
31
    if(t[o].mx <= tag) return;
32
    t[o].sum -= (t[o].mx - tag) * t[o].num;
33
    t[o].mx = t[o].tag = tag;
34
}
35
void pushdown(int o){
36
    if(t[o].tag == -1) return;
37
    change(ls, t[o].tag); change(rs, t[o].tag);
38
    t[o].tag = -1;
39
}
40
void build(int o, int l, int r){
41
    t[o].tag = -1; t[o].sec = -1;
42
    if(l == r){
43
        t[o].mx = t[o].sum = a[l];
44
        t[o].num = 1;
45
        return;
46
    }
47
    int mid = (l + r) >> 1;
48
    build(ls, l, mid); build(rs, mid + 1, r);
49
    pushup(o);
50
}
51
void update(int o, int l, int r, int cl, int cr, int k){
52
    if(cl > r || cr < l) return;
53
    if(cl <= l && r <= cr && t[o].sec <= k){
54
        change(o, k);
55
        return;
56
    }
57
    pushdown(o);
58
    int mid = (l + r) >> 1;
59
    if(cl <= mid) update(ls, l, mid, cl, cr, k);
60
    if(cr > mid) update(rs, mid + 1, r, cl, cr, k);
61
    pushup(o);
62
}
63
long long qrysum(int o, int l, int r, int ql, int qr){
64
    if(ql <= l && r <= qr) return t[o].sum;
65
    pushdown(o);
66
    int mid = (l + r) >> 1;
67
    long long res = 0;
68
    if(ql <= mid) res += qrysum(ls, l, mid, ql, qr);
69
    if(qr > mid) res += qrysum(rs, mid + 1, r, ql, qr);
70
    return res;
71
}
72
long long qrymx(int o, int l, int r, int ql, int qr){
73
    if(ql <= l && r <= qr) return t[o].mx;
74
    pushdown(o);
75
    int mid = (l + r) >> 1;
76
    long long res = -1;
77
    if(ql <= mid) res = max(res, qrymx(ls, l, mid ,ql, qr));
78
    if(qr > mid) res = max(res, qrymx(rs, mid + 1, r, ql, qr));
79
    return res;
80
}
81
void solve(){
82
    int n, m;
83
    scanf("%d%d", &n, &m);
84
    for(int i = 1; i <= n; i++){
85
        scanf("%lld", &a[i]);
86
    }
87
    build(1, 1, n);
88
    int opt, x, y, k;
89
    for(int i = 1; i <= m; i++){
90
        scanf("%d%d%d", &opt, &x, &y);
91
        if(opt == 0){
92
            scanf("%d", &k);
93
            update(1, 1, n, x, y, k);
94
        }
95
        else if(opt == 1){
96
            printf("%lld\n", qrymx(1, 1, n, x, y));
97
        }
98
        else if(opt == 2){
99
            printf("%lld\n", qrysum(1, 1, n, x, y));
100
        }
101
    }
102
}
103
int main(){
104
    int T;
105
    scanf("%d", &T);
106
    while(T--){
107
        solve();
108
    }
109
}