HDU 5306 Gorgeous Sequence

Problem Description

There is a sequence a of length n. We use ai to denote the i-th element in this sequence. You should do the following three types of operations to this sequence.

0 x y t: For every x≤i≤y, we use min(ai,t) to replace the original ai’s value.

1 x y: Print the maximum value of ai that x≤i≤y.

2 x y: Print the sum of ai that x≤i≤y.

Input

The first line of the input is a single integer T, indicating the number of testcases.

The first line contains two integers n and m denoting the length of the sequence and the number of operations.

The second line contains n separated integers a1,…,an (∀1≤i≤n,0≤ai<231).

Each of the following m lines represents one operation (1≤x≤y≤n,0≤t<231).

It is guaranteed that T=100, ∑n≤1000000, ∑m≤1000000.

Output

For every operation of type 1 or 2, print one line containing the answer to the corresponding query.

Sample Input

Sample Output

Hint

Please use efficient IO method

Author

XJZX

Source

2015 Multi-University Training Contest 2

wange2014 | We have carefully selected several similar problems for you: 6010 6009 6008 6007 6006

Solution

Segment Tree Beats! 的模板。

赶紧记下来Orz

把Tag和区间min合并起来，妙啊！

Code

  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
112
113
114
115
116
117
118
119
120
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <functional>
using namespace std;
const int maxn = 1000005;
const int INF = 1000000007;
inline int getint() {
    int r = 0; bool b = true; char c = getchar();
    for (; '0' > c || c > '9'; c = getchar()) if (c == '-') b = false;
    for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 + (c - '0');
    if (b) return r;
    return -r;
}
typedef long long LL;
int tmp[4], a[maxn];
LL ans;
struct node_t {
    node_t *lc, *rc;
    LL mx, se, cnt, sum;
    inline void upd(LL x) {
        if (x >= mx) return;
        sum += (x - mx) * cnt;
        mx = x;
    }
    inline void pushdown() {
        lc->upd(mx);
        rc->upd(mx);
    }
    inline void pushup() {
        tmp[0] = lc->mx;
        tmp[1] = rc->mx;
        tmp[2] = lc->se;
        tmp[3] = rc->se;
        sort(tmp, tmp+4, greater<LL>());
        mx = tmp[0];
        if (tmp[0] == tmp[1]) {
            se = tmp[2];
            cnt = lc->cnt + rc->cnt;
        } else {
            se = tmp[1];
            if (tmp[0] == lc->mx) cnt = lc->cnt;
            else cnt = rc->cnt;
        }
        sum = lc->sum + rc->sum;
    }
} *root, *dst = (node_t *)malloc(sizeof(node_t) * maxn * 2);
int tot;
void build(node_t *x, int l, int r) {
    if (l == r) {
        x->mx = a[l];
        x->se = -INF;
        x->cnt = 1;
        x->sum = a[l];
        x->lc = x->rc = NULL;
    } else {
        int mid = (l + r) >> 1;
        x->lc = dst + (tot++);
        x->rc = dst + (tot++);
        build(x->lc, l, mid);
        build(x->rc,mid+1,r);
        x->pushup();
    }
}

void change(node_t *x, int l, int r, int ll, int rr, int val) {
    if (val >= x->mx) return;
    if (ll <= l && r <= rr && x->se < val) { x->upd(val); return; }
    int mid = (l + r) >> 1;
    x->pushdown();
    if (ll <= mid) change(x->lc, l, mid, ll, rr, val);
    if (rr > mid) change(x->rc, mid+1, r, ll, rr, val);
    x->pushup();
}

void qmax(node_t *x, int l, int r, int ll, int rr) {
    if (x->mx <= ans) return;
    if (ll <= l && r <= rr) {
        ans = max(ans, x->mx);
        return;
    }
    x->pushdown();
    int mid = (l + r) >> 1;
    if (ll <= mid) qmax(x->lc, l, mid, ll, rr);
    if (rr > mid) qmax(x->rc, mid+1,r, ll, rr);
}

void qsum(node_t *x, int l, int r, int ll, int rr) {
    if (ll <= l && r <= rr) {
        ans += x->sum;
        return;
    }
    x->pushdown();
    int mid = (l + r) >> 1;
    if (ll <= mid) qsum(x->lc, l, mid, ll, rr);
    if (rr > mid) qsum(x->rc, mid+1,r, ll, rr);
}

int main() {
    int T = getint(), n, m, x, y, z, t;
    while (T--) {
        tot = 0;
        n = getint(); m = getint();
        for (int i = 1; i <= n; ++i) a[i] = getint();
        root = dst + (tot++);
        build(root, 1, n);
        while (m--) {
            t = getint();
            if (t == 0) {
                x = getint(); y = getint(); z = getint();
                change(root, 1, n, x, y, z);
            } else {
                x = getint(); y = getint(); ans = 0ll;
                if (t == 1) qmax(root, 1, n, x, y);
                else qsum(root, 1, n, x, y);
                printf("%lld\n", ans);
            }
        }
    }
}