BZOJ3064 CPU监控

发表于

  题意:维护一个序列，4个操作:

  1、区间加上x

  2、区间赋值为x

  3、询问区间最大值

  4、询问区间历史最大值

  区间历史最值，涉及到多次add和set操作的先后顺序，不是个好办的东西。
  参考吉如一2016集训队论文，发现了一个巧妙的做法。
  支持add和set操作的线段树有一个性质:
  当一次set操作之后，在下一次节点pushdown之前，由于此时区间均为一个数，所以区间add操作可以全部视为区间set。
  所以我们只需要考虑第一次set之前的add标记达到过的最值maxadd和后面的set标记达到过的最值maxset。
  至此问题已经解决。
  程序有点长，在过程中始终要牢记第一次set之后的add全部变成set，不管何处都是一样。

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <ctime>
  
using namespace std;
  
#define rep(i, l, r) for(int i = l, i##end = r; i <= i##end; ++i)
#define drep(i, l, r) for(int i = l, i##end = r; i >= i##end; --i)
#define ms(a, b) memset(a, b, sizeof a)
  
template<class T> inline bool chkmax(T& a, T b) { return a < b ? a = b, 1 : 0; }
template<class T> inline bool chkmin(T& a, T b) { return a > b ? a = b, 1 : 0; }
  
template<typename T> inline T& read(T& x)
{
    static char c; bool flag = 0;
    while(!isdigit(c = getchar())) if(c == '-') flag = 1;
    for(x = c ^ 48; isdigit(c = getchar()); x = (x << 3) + (x << 1) + (c ^ 48));
    if(flag) x = -x; return x;
}
 
const int maxn = 100010, INF = 0x3f3f3f3f;
 
int n, m;
 
namespace SGT
{
#define ls h << 1
#define rs h << 1 | 1
#define mid ((l + r) >> 1)
#define lc l, mid
#define rc mid + 1, r
 
    int Max[maxn * 3], PastMax[maxn * 3];
    int add[maxn * 3], set[maxn * 3], pastadd[maxn * 3], pastset[maxn * 3];
 
    void pushup(int h)
    {
        Max[h] = max(Max[ls], Max[rs]);
        PastMax[h] = max(PastMax[ls], PastMax[rs]);
    }
 
    void creat(int h, int l, int r)
    {
        set[h] = pastset[h] = -INF;
        if(l == r) { PastMax[h] = read(Max[h]); return; }
        creat(ls, lc); creat(rs, rc);
        pushup(h);
    }
 
    void pushdown(int h)
    {
        if(pastadd[h])
        {
            chkmax(PastMax[ls], Max[ls] + pastadd[h]);
            if(pastset[ls] == -INF) chkmax(pastadd[ls], add[ls] + pastadd[h]);
            else chkmax(pastset[ls], set[ls] + pastadd[h]);
 
            chkmax(PastMax[rs], Max[rs] + pastadd[h]);
            if(pastset[rs] == -INF) chkmax(pastadd[rs], add[rs] + pastadd[h]);
            else chkmax(pastset[rs], set[rs] + pastadd[h]);
 
            pastadd[h] = 0;
        }
 
        if(pastset[h] != -INF)
        {
            chkmax(PastMax[ls], pastset[h]);
            chkmax(pastset[ls], pastset[h]);
            chkmax(PastMax[rs], pastset[h]);
            chkmax(pastset[rs], pastset[h]);
 
            pastset[h] = -INF;
        }
 
        if(set[h] != -INF)
        {
            Max[ls] = Max[rs] = set[h]; 
            set[ls] = set[rs] = set[h];
			add[ls] = add[rs] = 0;
            set[h] = -INF;
        }
 
        if(add[h])
        {
            Max[ls] += add[h], Max[rs] += add[h];
			if(pastset[ls] == -INF) add[ls] += add[h];
			else set[ls] += add[h];
			if(pastset[rs] == -INF) add[rs] += add[h];
			else set[rs] += add[h];
            add[h] = 0;
        }
    }
 
    void upd_add(int h, int l, int r, int L, int R, int x)
    {
        if(L <= l && r <= R)
        {
            Max[h] += x;
            chkmax(PastMax[h], Max[h]);
            if(pastset[h] == -INF)
			{
				add[h] += x;
				chkmax(pastadd[h], add[h]);
			}
            else
			{
				set[h] += x;
				chkmax(pastset[h], set[h]);
			}
            return;
        }
        pushdown(h);
        if(L <= mid) upd_add(ls, lc, L, R, x);
        if(R > mid) upd_add(rs, rc, L, R, x);
        pushup(h);
    }
 
    void upd_set(int h, int l, int r, int L, int R, int x)
    {
        if(L <= l && r <= R)
        {
            Max[h] = set[h] = x; add[h] = 0;
            chkmax(PastMax[h], Max[h]);
            chkmax(pastset[h], set[h]);
            return;
        }
        pushdown(h);
        if(L <= mid) upd_set(ls, lc, L, R, x);
        if(R > mid) upd_set(rs, rc, L, R, x);
        pushup(h);
    }
 
    int query(int h, int l, int r, int L, int R, bool op)
    {
        if(L <= l && r <= R) return op ? Max[h] : PastMax[h];
        pushdown(h); int ret = -INF;
        if(L <= mid) chkmax(ret, query(ls, lc, L, R, op));
        if(R > mid) chkmax(ret, query(rs, rc, L, R, op));
        return ret;
    }
}
using namespace SGT;
 
int main()
{
#ifndef ONLINE_JUDGE
	freopen("exec.in", "r", stdin); freopen("exec.out", "w", stdout);
#endif
    read(n); creat(1, 1, n);
    read(m);
    while(m--)
    {
        char op[2]; int l, r, w;
		scanf("%s", op); read(l), read(r);
        if(op[0] == 'P') read(w), upd_add(1, 1, n, l, r, w);
        else if(op[0] == 'C') read(w), upd_set(1, 1, n, l, r, w);
        else printf("%d\n", query(1, 1, n, l, r, op[0] == 'Q'));
    }
 
    return 0;
}