「UOJ 164」「清华集训2015」V

UOJ #164

题意

给出一个长度为\(n\)的数列\(a\),需要维护以下操作

  1. 对于\(i\in[l,r]\)\(a_i=a_i+x\)

  2. 对于\(i\in[l,r]\)\(a_i=max(a_i-x,0)\)

  3. 对于\(i\in[l,r]\)\(a_i=x\)

  4. 询问\(a_y\)

  5. 询问\(a_y\)的历史最大值

\(n,m\le 5*10^5,0\le a_i,x\le10^9\)


分析

定义标记\((x,y)\)表示先\(+x\)再对\(y\)\(max\)

前三种操作可以转化为

  1. \((x,0)\)
  2. \((-x,0)\)
  3. \((-inf,x)\)

标记是可以合并的。把时间较晚的\((c,d)\)合并到\((a,b)\)上,得到标记\((a+c,max(b+c,d))\)

每个节点维护标记\((add,mx)\),和上次\(pushdown\)该节点之后到现在,标记两部分的历史最大值\((madd,mmx)\)

带历史最大值标记的下传具体参考代码

每次查询下传到底就好了

注意\(add\)标记\(-inf\)时不要爆了

时间复杂度 \(\mathcal O(m\log n)\)


代码

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
#include<cstdio>
#include<algorithm>
#include<ctype.h>
#include<string.h>
#include<math.h>

using namespace std;
#define ll long long

inline char read() {
static const int IN_LEN = 1000000;
static char buf[IN_LEN], *s, *t;
return (s == t ? t = (s = buf) + fread(buf, 1, IN_LEN, stdin), (s == t ? -1 : *s++) : *s++);
}
template<class T>
inline void read(T &x) {
static bool iosig;
static char c;
for (iosig = false, c = read(); !isdigit(c); c = read()) {
if (c == '-') iosig = true;
if (c == -1) return;
}
for (x = 0; isdigit(c); c = read()) x = ((x + (x << 2)) << 1) + (c ^ '0');
if (iosig) x = -x;
}
const int OUT_LEN = 10000000;
char obuf[OUT_LEN], *ooh = obuf;
inline void print(char c) {
if (ooh == obuf + OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), ooh = obuf;
*ooh++ = c;
}
template<class T>
inline void print(T x) {
static int buf[30], cnt;
if (x == 0) print('0');
else {
if (x < 0) print('-'), x = -x;
for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 + 48;
while (cnt) print((char)buf[cnt--]);
}
}
inline void flush() { fwrite(obuf, 1, ooh - obuf, stdout); }

const int N = 500005;
const ll inf = 1e16;
int n, m, a[N];
ll add[N<<2], madd[N<<2], mx[N<<2], mmx[N<<2];
inline void chkmx(ll &x, ll y){ x<y?x=y:0;}
inline void pushdown(int t){
int k=t<<1;
chkmx(madd[k], add[k]+madd[t]);
chkmx(mmx[k], max(mmx[t], mx[k]+madd[t]));
chkmx(add[k]+=add[t], -inf);
mx[k]=max(mx[t], mx[k]+add[t]);
chkmx(madd[k|1], add[k|1]+madd[t]);
chkmx(mmx[k|1], max(mmx[t], mx[k|1]+madd[t]));
chkmx(add[k|1]+=add[t], -inf);
mx[k|1]=max(mx[t], mx[k|1]+add[t]);
add[t]=madd[t]=mx[t]=mmx[t]=0;
}
void build(int l, int r, int t){
if(l==r) return (void)(add[t]=madd[t]=a[l]);
int mid=l+r>>1, k=t<<1;
build(l, mid, k), build(mid+1, r, k|1);
}
void change(int l, int r, int t, int L, int R, ll x, ll y){
if(L<=l && r<=R) return chkmx(madd[t], add[t]+=x), chkmx(mmx[t], mx[t]=max(mx[t]+x, y));
int mid=l+r>>1, k=t<<1;
pushdown(t);
if(L<=mid) change(l, mid, k, L, R, x, y);
if(R>mid) change(mid+1, r, k|1, L, R, x, y);
}
ll query(int l, int r, int t, int pos, bool opt){
if(l==r) return opt?max(madd[t], mmx[t]):max(add[t], mx[t]);
int mid=l+r>>1, k=t<<1;
pushdown(t);
return pos<=mid?query(l, mid, k, pos, opt):query(mid+1, r, k|1, pos, opt);
}
int main() {
read(n), read(m);
for(int i=1; i<=n; ++i) read(a[i]);
build(1, n, 1);
while(m--){
static int opt, l, r, x;
read(opt), read(l);
if(opt<=3){
read(r), read(x);
if(opt==1) change(1, n, 1, l, r, x, 0);
else if(opt==2) change(1, n, 1, l, r, -x, 0);
else change(1, n, 1, l, r, -inf, x);
}
else print(query(1, n, 1, l, opt-4)), print('\n');
}
return flush(), 0;
}