AK-dream

好久没写题解了 来水一篇题解

题目描述

请写一个程序,要求维护一个数列,支持以下 6 种操作:

输入格式

输入的第1行包含两个数 $N$ 和 $M(M \leq 20 000)$,$N$ 表示初始时数列中数的个数,$M$ 表示要进行的操作数目。

第2行包含 $N$ 个数字,描述初始时的数列。

以下 $M$ 行,每行一条命令,格式参见问题描述中的表格。

任何时刻数列中最多含有 $500000$ 个数,数列中任何一个数字均在 $[-1 000, 1 000]$ 内。

插入的数字总数不超过 $4 000 000$ 个,输入文件大小不超过20MB。

输出格式

对于输入数据中的GET-SUM和MAX-SUM操作,向输出文件依次打印结果,每个答案(数字)占一行。

题解

一道平衡树维护各种标记以及pushup,pushdown的模板题?

我这里用的是飞旋非旋Treap,Splay也可以做,但是显然非旋Treap要比较好写

维护最大子段和的套路就是维护区间最大前缀和以及最大后缀和,pushup时:

最大前缀和 = max(左儿子最大前缀和,左儿子区间和+当前节点权值+右儿子最大前缀和)
最大后缀和 = max(右儿子最大后缀和,右儿子区间和+当前节点权值+左儿子最大后缀和)
最大子段和 = max( max(左儿子最大子段和,右儿子最大子段和),左儿子最大后缀和+当前节点权值+右儿子最大前缀和)

此题细节特别多:

  • 最大子段不能为空 所以修改时要注意不能让它不含任何元素而子段和等于 $0$ ,尤其是pushup的时候注意

  • 最大前缀和以及最大后缀和可以为空,所以最小也是 $0$ ,不会为负

  • 覆盖标记的初始值不能设成 $0$ !因为一次操作可能会要求把一段区间全部赋为 $0$ ,可以把覆盖标记初始值设成inf

  • 区间翻转的时候,不光要交换左右儿子,还要交换最大前缀和与最大后缀和!

  • 在树的结构即将发生变化时,一定要记得先pushdown!

代码

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
#include <bits/stdc++.h>
#define N 500005
#define M 4000005
using namespace std;

template<typename T>
inline void read(T &num) {
T x = 0, f = 1; char ch = getchar();
for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') f = -1;
for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ '0');
num = x * f;
}

int n, m, nowtot;
int rt, tot, siz[M], val[M], rnd[M], ch[M][2], tag[M], rev[M];
int mx[M], sum[M], lmx[M], rmx[M];
const int inf = 0x7fffffff;

inline int newnode(int v) {
tot++;
siz[tot] = 1; val[tot] = sum[tot] = v; rnd[tot] = rand();
ch[tot][0] = ch[tot][1] = 0; tag[tot] = inf; rev[tot] = 0;
lmx[tot] = rmx[tot] = max(0, v); mx[tot] = v;
return tot;
}

inline void pushup(int x) {
siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + 1;
sum[x] = sum[ch[x][0]] + sum[ch[x][1]] + val[x];
lmx[x] = max(lmx[ch[x][0]], sum[ch[x][0]] + val[x] + lmx[ch[x][1]]);
rmx[x] = max(rmx[ch[x][1]], sum[ch[x][1]] + val[x] + rmx[ch[x][0]]);
lmx[x] = max(lmx[x], 0); rmx[x] = max(rmx[x], 0);
mx[x] = rmx[ch[x][0]] + val[x] + lmx[ch[x][1]];
if (ch[x][0]) mx[x] = max(mx[x], mx[ch[x][0]]);
if (ch[x][1]) mx[x] = max(mx[x], mx[ch[x][1]]);
}

inline void change(int x, int v) {
val[x] = v;
sum[x] = siz[x] * v;
lmx[x] = rmx[x] = max(0, siz[x] * v);
mx[x] = max(v, siz[x] * v);
tag[x] = v;
}

inline void Rev(int x) {
swap(lmx[x], rmx[x]);
swap(ch[x][0], ch[x][1]);
rev[x] ^= 1;
}

inline void pushdown(int x) {
if (tag[x] != inf) {
int v = tag[x]; tag[x] = inf;
if (ch[x][0]) change(ch[x][0], v);
if (ch[x][1]) change(ch[x][1], v);
}
if (rev[x]) {
if (ch[x][0]) Rev(ch[x][0]);
if (ch[x][1]) Rev(ch[x][1]);
rev[x] = 0;
}
}

void split(int now, int k, int &x, int &y) {
if (!now) {
x = y = 0; return;
}
pushdown(now);
if (k > siz[ch[now][0]]) {
x = now; split(ch[now][1], k - siz[ch[now][0]] - 1, ch[now][1], y);
} else {
y = now; split(ch[now][0], k, x, ch[now][0]);
}
pushup(now);
}

int merge(int x, int y) {
if (!x || !y) return x | y;
pushdown(x); pushdown(y);
if (rnd[x] < rnd[y]) {
ch[x][1] = merge(ch[x][1], y);
pushup(x);
return x;
} else {
ch[y][0] = merge(x, ch[y][0]);
pushup(y);
return y;
}
}

char s[50];

int main() {
srand(time(NULL));
read(n); read(m);
for (int i = 1, v, x, y; i <= n; i++) {
read(v); x = y = 0;
split(rt, i - 1, x, y);
rt = merge(merge(x, newnode(v)), y);
}
nowtot = n;
for (int i = 1; i <= m; i++) {
scanf("%s", s);
int pos = 0, cnt = 0, v = 0, x = 0, y = 0, z = 0;
if (s[0] == 'I') {
read(pos); read(cnt);
nowtot += cnt;
split(rt, pos, x, y);
for (int j = 1; j <= cnt; j++) {
read(v);
x = merge(x, newnode(v));
}
rt = merge(x, y);
} else if (s[0] == 'D') {
read(pos); read(cnt);
nowtot -= cnt;
split(rt, pos - 1, x, y);
split(y, cnt, y, z);
rt = merge(x, z);
} else if (s[0] == 'R') {
read(pos); read(cnt);
split(rt, pos - 1, x, y);
split(y, cnt, y, z);
Rev(y);
rt = merge(x, merge(y, z));
} else if (s[0] == 'G') {
read(pos); read(cnt);
split(rt, pos - 1, x, y);
split(y, cnt, y, z);
printf("%d\n", sum[y]);
rt = merge(x, merge(y, z));
} else if (s[2] == 'K') {
read(pos); read(cnt); read(v);
split(rt, pos - 1, x, y);
split(y, cnt, y, z);
change(y, v);
rt = merge(x, merge(y, z));
} else {
printf("%d\n", mx[rt]);
}
}
return 0;
}

 评论