Tyvj 1518 CPU监控

发表于 | 分类于

题目

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

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

OUTPUT

79
-70
-70
-5
79
10
10
79
79
-5
10
10

解题报告

这道极其简（e）单（xin），真的是一道裸（zhi）的（zhang）线段树。
首先，我们需要维护各种奇奇怪怪的域，当前和，当前最大值，历史和，历史最大值，而历史值又不包括当前值，这就导致了lazy操作的pushdown极其好（nan）写。
没有什么好多说的，直接看这个极其漂（chou）亮（lou）的代码= =

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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int inf=1<<31;
inline int read(){
    int sum(0),f(1);
    char ch(getchar());
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        sum=sum*10+ch-'0';
        ch=getchar();
    }
    return sum*f;
}
int n,m;
int v[100001];
int padd[400001],pset[400001],pmx[400001];
int nadd[400001],nset[400001],nmx[400001];
inline int my_max(int a,int b){
    return a>b?a:b;
}
inline void pushup(int i){
    int l(i<<1),r(l|1);
    pmx[i]=my_max(pmx[l],pmx[r]);
    nmx[i]=my_max(nmx[l],nmx[r]);
}
inline void pushdown(int rt){
    int ch(rt<<1);
    for(int i=0;i<=1;i++){
        int nowch(ch+i);
        pmx[nowch]=my_max(pmx[nowch],my_max(padd[rt]+nmx[nowch],pset[rt]));
        if(nset[rt]==inf){
            nmx[nowch]+=nadd[rt];
            if(nset[nowch]==inf){
                padd[nowch]=my_max(padd[nowch],nadd[nowch]+padd[rt]);
                nadd[nowch]+=nadd[rt];
            }
            else{
                pset[nowch]=my_max(pset[nowch],nset[nowch]+padd[rt]);
                nset[nowch]=nmx[nowch];
            }
        }
        else{
            if(nset[nowch]==inf){
                padd[nowch]=my_max(padd[nowch],nadd[nowch]+padd[rt]);
                nadd[nowch]+=padd[rt];
            }
            else
                pset[nowch]=my_max(pset[nowch],nmx[nowch]+padd[rt]);
            nmx[nowch]=nset[rt];
            nset[nowch]=nset[rt];
            pset[nowch]=my_max(pset[rt],pset[nowch]);
        }
    }
    nadd[rt]=0;
    padd[rt]=0;
    nset[rt]=inf;
    pset[rt]=inf;
}
inline void build(int l,int r,int i){
    padd[i]=0;
    pset[i]=inf;
    nadd[i]=0;
    nset[i]=inf;
    if(l==r){
        pmx[i]=v[l];
        nmx[i]=v[l];
        return;
    }
    int lc(i<<1),rc(lc|1),mid((l+r)>>1);
    build(l,mid,lc);
    build(mid+1,r,rc);
    pushup(i);
}
inline void update_set(int ll,int rr,int c,int l,int r,int i){
    if(ll<=l&&r<=rr){
        nset[i]=c;
        nmx[i]=c;
        pset[i]=my_max(pset[i],nset[i]);
        pmx[i]=my_max(pmx[i],nmx[i]);
        return;
    }
    pushdown(i);
    int lc(i<<1),rc(lc|1),mid((l+r)>>1);
    if(ll<=mid)
        update_set(ll,rr,c,l,mid,lc);
    if(rr>mid)
        update_set(ll,rr,c,mid+1,r,rc);
    pushup(i);
}
inline void update_add(int ll,int rr,int c,int l,int r,int i){
    if(ll<=l&&r<=rr){
        nmx[i]+=c;
        pmx[i]=my_max(pmx[i],nmx[i]);
        if(nset[i]==inf){
            nadd[i]+=c;
            padd[i]=my_max(padd[i],nadd[i]);
        }
        else{
            nset[i]=nmx[i];
            pset[i]=my_max(pset[i],nset[i]);
        }
        return;
    }
    pushdown(i);
    int lc(i<<1),rc(lc|1),mid((l+r)>>1);
    if(ll<=mid)
        update_add(ll,rr,c,l,mid,lc);
    if(rr>mid)
        update_add(ll,rr,c,mid+1,r,rc);
    pushup(i);
}
inline int query_p(int ll,int rr,int l,int r,int i){
    if(ll<=l&&r<=rr)
        return pmx[i];
    pushdown(i);
    int lc(i<<1),rc(lc|1),mid((l+r)>>1);
    int ret(inf);
    if(ll<=mid)
        ret=my_max(ret,query_p(ll,rr,l,mid,lc));
    if(rr>mid)
        ret=my_max(ret,query_p(ll,rr,mid+1,r,rc));
    return ret;
}
inline int query_n(int ll,int rr,int l,int r,int i){
    if(ll<=l&&r<=rr)
        return nmx[i];
    pushdown(i);
    int lc(i<<1),rc(lc|1),mid((l+r)>>1);
    int ret(inf);
    if(ll<=mid)
        ret=my_max(ret,query_n(ll,rr,l,mid,lc));
    if(rr>mid)
        ret=my_max(ret,query_n(ll,rr,mid+1,r,rc));
    return ret;
}
int main(){
    n=read();
    for(int i=1;i<=n;i++)
        v[i]=read();
    /*for(int i=1;i<=n;i++)
        cout<<v[i]<<' ';*/
    build(1,n,1);
    m=read();
    char op[2];
    while(m--){
        scanf("%s",op);
        if(op[0]=='Q'){
            int x(read()),y(read());
            printf("%d\n",query_n(x,y,1,n,1));
            continue;
        }
        if(op[0]=='A'){
            int x(read()),y(read());
            printf("%d\n",query_p(x,y,1,n,1));
            continue;
        }
        if(op[0]=='P'){
            int x(read()),y(read()),z(read());
            update_add(x,y,z,1,n,1);
            continue;
        }
        if(op[0]=='C'){
            int x(read()),y(read()),z(read());
            update_set(x,y,z,1,n,1);
            continue;
        }
    }//while(1);
}

ps:本以为可以写到200行，后来pushdown强行压了一半，然后各种压行，形成了如此漂（chou）亮（lou）的代码风格= =