BZOJ 3064: Tyvj 1518 CPU监控

Description

Bob需要一个程序来监视CPU使用率。这是一个很繁琐的过程，为了让问题更加简单，Bob会慢慢列出今天会在用计算机时做什么事。

Bob会干很多事，除了跑暴力程序看视频之外，还会做出去玩玩和用鼠标乱点之类的事，甚至会一脚踢掉电源……这些事有的会让做这件事的这段时间内CPU使用率增加或减少一个值；有的事还会直接让CPU使用率变为一个值。

当然Bob会询问：在之前给出的事件影响下，CPU在某段时间内，使用率最高是多少。有时候Bob还会好奇地询问，在某段时间内CPU曾经的最高使用率是多少。

为了使计算精确，使用率不用百分比而用一个整数表示。

不保证Bob的事件列表出了莫名的问题，使得使用率为负………………

Input

第一行一个正整数T，表示Bob需要监视CPU的总时间。

然后第二行给出T个数表示在你的监视程序执行之前，Bob干的事让CPU在这段时间内每个时刻的使用率达已经达到了多少。

第三行给出一个数E，表示Bob需要做的事和询问的总数。

接下来E行每行表示给出一个询问或者列出一条事件：

Q X Y:询问从X到Y这段时间内CPU最高使用率
A X Y:询问从X到Y这段时间内之前列出的事件使CPU达到过的最高使用率
P X Y Z:列出一个事件这个事件使得从X到Y这段时间内CPU使用率增加Z
C X Y Z:列出一个事件这个事件使得从X到Y这段时间内CPU使用率变为Z

时间的单位为秒，使用率没有单位。

X和Y均为正整数（X<=Y），Z为一个整数。

从X到Y这段时间包含第X秒和第Y秒。

保证必要运算在有符号32位整数以内。

Output

对于每个询问，输出一行一个整数回答。

Sample Input

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
10
-62 -83 -9 -70 79 -78 -31 40 -18 -5 
20
A 2 7
A 4 4
Q 4 4
P 2 2 -74
P 7 9 -71
P 7 10 -8
A 10 10
A 5 9
C 1 8 10
Q 6 6
Q 8 10
A 1 7
P 9 9 96
A 5 5
P 8 10 -53
P 6 6 5
A 10 10
A 4 4
Q 1 5
P 4 9 -69

Sample Output

Constraint

数据分布如下：

第1、2个数据保证T和E均小于等于1000

第3、4个数据保证只有Q类询问

第5、6个数据保证只有C类事件

第7、8个数据保证只有P类事件

全部数据保证T和E均小于等于100000

Source

tyvj 1518

Solution

线段树。

CPU分治

考虑到对于一条线段的所有操作都可以整合为先加后整体赋值的操作，于是我们可以把所有的操作都整合起来。

标记的合并比较恶心，实际上需要维护7个tag，分别是当前max、set、add，历史最大max、set、add和是否被整体赋值了。

注意set的优先级高于add，也就是先set后add。

下传标记的时候，我们需要先下传add标记，因为这个标记作用时间比set要靠前。

第一次提交的时候，居然忘记下传add标记了 >_< …

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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 100005;
const int INF = 2147483647;
int qans, a[maxn], n;
struct Node {
    int mx, set, add, hmx, hset, hadd;
    bool is_set;
    Node *lc, *rc;
    inline void pushup() {
        mx = max(lc->mx, rc->mx);
        hmx = max(lc->hmx, rc->hmx);
    }
    inline void ADD(int val, int fval) {
        if (is_set) {
            hset = max(hset, set + fval);
            set += val;
        }
        else {
            hadd = max(hadd, add + fval);
            add += val;
        }
        hmx = max(hmx, mx + fval);
        mx += val;
    }
    inline void SET(int val, int fval) {
        if (is_set) {
            hset = max(hset, fval);
            set = val;
        }
        else {
            add = 0;
            is_set = true;
            hset = fval;
            set = val;
        }
        hmx = max(hmx, fval);
        mx = val;
    }
    inline void pushdown() {
        lc->ADD(add, hadd);
        rc->ADD(add, hadd);
        if (is_set) {
            lc->SET(set, hset);
            rc->SET(set, hset);
        }
        is_set = false;
        add = hadd = 0;
    }
} *rt, node[maxn*2];
int tot;
Node *build(int l, int r) {
    Node *ret = node + (tot++);
    ret->is_set = false;
    ret->add = ret->hadd = 0;
    if (l == r) ret->mx = ret->hmx = a[l];
    else {
        int mid = (l + r) >> 1;
        ret->lc = build(l, mid);
        ret->rc = build(mid + 1, r);
        ret->pushup();
    }
    return ret;
}
void add(Node *x, int l, int r, int ll, int rr, int v) {
    if (ll <= l && r <= rr) x->ADD(v, v);
    else {
        x->pushdown();
        int mid = (l + r) >> 1;
        if (ll <= mid) add(x->lc, l, mid, ll, rr, v);
        if (rr > mid) add(x->rc, mid+1, r, ll, rr, v);
        x->pushup();
    }
}
void set(Node *x, int l, int r, int ll, int rr, int v) {
    if (ll <= l && r <= rr) x->SET(v, v);
    else {
        x->pushdown();
        int mid = (l + r) >> 1;
        if (ll <= mid) set(x->lc, l, mid, ll, rr, v);
        if (rr > mid) set(x->rc, mid+1, r, ll, rr, v);
        x->pushup();
    }
}
void ask_max(Node *x, int l, int r, int ll, int rr) {
    if (qans >= x->mx) return;
    if (ll <= l && r <= rr) qans = x->mx;
    else {
        x->pushdown();
        int mid = (l + r) >> 1;
        if (ll <= mid) ask_max(x->lc, l, mid, ll, rr);
        if (rr > mid) ask_max(x->rc, mid+1, r, ll, rr);
    }
}
void ask_hmax(Node *x, int l, int r, int ll, int rr) {
    if (qans >= x->hmx) return;
    if (ll <= l && r <= rr) qans = x->hmx;
    else {
        x->pushdown();
        int mid = (l + r) >> 1;
        if (ll <= mid) ask_hmax(x->lc, l, mid, ll, rr);
        if (rr > mid) ask_hmax(x->rc, mid+1, r, ll, rr);
    }
}
inline int getint() {
    int r = 0; bool b = true; char c = getchar();
    while ('0' > c || c > '9') { if (c == '-') b = false; c = getchar(); }
    while ('0' <= c && c <= '9') { r = r * 10 + (c - '0'); c = getchar(); }
    if (b) return r;
    return -r;
}
char str[3];
int m, x, y, z;
int main() {
    n = getint();
    for (int i = 1, *aa = a + 1; i <= n; ++i, ++aa) (*aa) = getint();
    rt = build(1, n);
    m = getint();
    while (m--) {
        scanf("%s", str);
        x = getint(); y = getint();
        if (str[0] == 'Q') {
            qans = -INF;
            ask_max(rt, 1, n, x, y);
            printf("%d\n", qans);
        }
        else if (str[0] == 'A') {
            qans = -INF;
            ask_hmax(rt, 1, n, x, y);
            printf("%d\n", qans);
        }
        else {
            z = getint();
            if (str[0] == 'P') add(rt, 1, n, x, y, z);
            else set(rt, 1, n, x, y, z);
        }
    }
}