网上好像没大有数组版FHQTreap的板子, 我就自己写了一个,模板题, 很短, 一个小时才写好, 码力太弱了;

题目大意

一个ZZ数据结构,能够进行这几个操作: 1. 区间覆盖 2. 区间求和 3. 区间翻转 4. 区间插入 5. 区间删除 6. 全局最大连续字段和

解题报告

用FHQTreap写的, 思路很清晰;

FHQTreap的精髓在于splitmerge操作,>FHQTreap的精髓在于splitmerge操作, split操作比较显然, 是把平衡树沿一个rank切开, merge借鉴了可并堆的操作, 但是因为Treap的平衡树特性, 不能像左偏树那样一遍倒;

FHQTreap是从上向下操作的一棵树, 需要像线段树一样, 下传先于访问, 当然,mergesplit改变树形态的时候, 需要push_up;<

垃圾回收和内存池与splay的写法一模一样,程序跑得不快, 但与splay比, 完全没有被卡常的机会;

代码

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
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define FORU(i, a, b) for (int i = a, nn = int(b); i <= nn; ++i)
#define FORD(i, a, b) for (int i = a, nn = int(b); i >= nn; --i)
#define REP(i, b) for (int i = 0, nn = int(b); i < nn; ++i)
#define sz(x) (int)(x).size()
#define RAND (rand()<<15|rand())
typedef long long ll;
const int inf = 1000000000;
const int N = 500010;
struct node {
int l, r, sz, lmx, rmx, tmx, key, v, cov, rev, sm;
} t[N];
queue<int> trash;
inline void in(int &x) {
char ch = getchar(); int f = 1;
for(; ch < '0' || ch > '9'; ch = getchar())
if (ch == '-') f = -1;
for (x = 0; ch >= '0' && ch <= '9'; ch = getchar())
x = x * 10 + ch - 48;
x *= f;
}
int root, tot;
inline void newnode(int &x, int val) {
if (!trash.empty()) {
x = trash.front(); trash.pop();
} else x = ++tot;
t[x].rev = 0, t[x].l = t[x].r = 0;
t[x].key = RAND, t[x].cov = inf;
t[x].v = t[x].sm = t[x].tmx = val;
t[x].lmx = t[x].rmx = max(val, 0);
t[x].sz = 1;
}
inline void push_up(node &x) {
if (x.l && x.r) {
x.sz = 1 + t[x.l].sz + t[x.r].sz;
x.sm = x.v + t[x.l].sm + t[x.r].sm;
x.tmx = max(t[x.l].tmx, t[x.r].tmx);
x.tmx = max(x.tmx, t[x.l].rmx + x.v + t[x.r].lmx);
x.lmx = max(t[x.l].lmx, t[x.l].sm + x.v + t[x.r].lmx);
x.rmx = max(t[x.r].rmx, t[x.r].sm + x.v + t[x.l].rmx);
} else
if (x.l) {
x.sz = 1 + t[x.l].sz;
x.sm = x.v + t[x.l].sm;
x.tmx = max(t[x.l].tmx, t[x.l].rmx + x.v);
x.lmx = max(t[x.l].lmx, t[x.l].sm + x.v);
x.lmx = max(0, x.lmx);
x.rmx = max(0, x.v + t[x.l].rmx);
} else
if (x.r) {
x.sz = 1 + t[x.r].sz;
x.sm = x.v + t[x.r].sm;
x.tmx = max(t[x.r].tmx, x.v + t[x.r].lmx);
x.lmx = max(0, x.v + t[x.r].lmx);
x.rmx = max(t[x.r].rmx, x.v + t[x.r].sm);
x.rmx = max(0, x.rmx);
} else {
x.sz = 1, x.sm = x.tmx = x.v;
x.lmx = x.rmx = max(x.v, 0);
}
}
inline void reversify(int x) {
swap(t[x].l, t[x].r);
swap(t[x].lmx, t[x].rmx);
t[x].rev ^= 1;
}
inline void coverify(int x, int v) {
t[x].v = v, t[x].sm = t[x].sz * v;
t[x].lmx = t[x].rmx = max(0, v*t[x].sz);
t[x].tmx = max(v, v * t[x].sz);
t[x].cov = v;
}
inline void push_down(node &x) {
if (x.rev) {
if (x.l) reversify(x.l);
if (x.r) reversify(x.r);
}
if (x.cov != inf) {
if (x.l) coverify(x.l, x.cov);
if (x.r) coverify(x.r, x.cov);
}
x.rev = 0, x.cov = inf;
}
inline int build(int *a, int n) {
int x, last = 0; static int sta[500010], top;
FORU(i, 1, n) {
newnode(x, a[i]); last = 0;
while (top && t[sta[top]].key > t[x].key) {
push_up(t[sta[top]]), last = sta[top];
sta[top -- ] = 0;
}
if (top) t[sta[top]].r = x;
t[x].l = last, sta[++top] = x;
}
while (top) push_up(t[sta[top --]]) ;
return sta[1];
}
pii split(int x, int k) {
if (!x) return mp(0, 0);
push_down(t[x]); pii y;
int tmp = t[ t[x].l ].sz;
if (tmp >= k) {
y = split(t[x].l, k);
t[x].l = y.se, push_up(t[x]);
y.se = x;
} else {
y = split(t[x].r, k - tmp - 1);
t[x].r = y.fi, push_up(t[x]);
y.fi = x;
}
return y;
}
int merge(int a, int b) {
if (a * b == 0) return a + b;
push_down(t[a]), push_down(t[b]);
if (t[a].key < t[b].key) {
t[a].r = merge(t[a].r, b);
push_up(t[a]); return a;
} else {
t[b].l = merge(a, t[b].l);
push_up(t[b]); return b;
}
}
void movetotrash(int x) {
if (!x) return;
trash.push(x);
movetotrash(t[x].l);
movetotrash(t[x].r);
}
inline void insert() {
int pos, tot; static int c[500010];
in(pos), in(tot); FORU(i, 1, tot) in(c[i]);
int rt = build(c, tot);
pii droot = split(root, pos);
root = merge(droot.fi, rt);
root = merge(root, droot.se);
}
inline void delet() {
int pos, tot; in(pos), in(tot);
pii dleft = split(root, pos-1);
pii dright = split(dleft.se, tot);
root = merge(dleft.fi, dright.se);
movetotrash(dright.fi);
}
inline void same() {
int pos, tot, c; in(pos), in(tot), in(c);
pii dleft = split(root, pos-1);
pii dright = split(dleft.se, tot);
coverify(dright.fi, c);
dleft.se = merge(dright.fi, dright.se);
root = merge(dleft.fi, dleft.se);
}
inline void reverse() {
int pos, tot; in(pos), in(tot);
pii dleft = split(root, pos - 1);
pii dright = split(dleft.se, tot);
reversify(dright.fi);
dleft.se = merge(dright.fi, dright.se);
root = merge(dleft.fi, dleft.se);
}
inline void getsum() {
int pos, tot; in(pos), in(tot);
pii dleft = split(root, pos - 1);
pii dright = split(dleft.se, tot);
printf("%d\n", t[dright.fi].sm);
dleft.se = merge(dright.fi, dright.se);
root = merge(dleft.fi, dleft.se);
}
inline void maxsum() {
printf("%d\n", t[root].tmx);
}
int main() {
static int n, m, a[N];
in(n), in(m); FORU(i, 1, n) in(a[i]);
root = build(a, n);
static char s[20];
while (m--) {
scanf("%s", s);
if (s[0] == 'I') insert();
else if (s[0] == 'D') delet();
else if (s[0] == 'M' && s[2] == 'K') same();
else if (s[0] == 'R') reverse();
else if (s[0] == 'G') getsum();
else maxsum();
}
return 0;
}



# 原题 题目链接

Problem 1500. – [NOI2005]维修数列

1500: [NOI2005]维修数列

Description

Input

输入的第1 行包含两个数N 和M(M ≤20 000),N 表示初始时数列中数的个数,M表示要进行的操作数目。
第2行包含N个数字,描述初始时的数列。
以下M行,每行一条命令,格式参见问题描述中的表格。
任何时刻数列中最多含有500 000个数,数列中任何一个数字均在[-1 000, 1 000]内。
插入的数字总数不超过4 000 000个,输入文件大小不超过20MBytes。

Output

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

Sample Input

        <div class="content"><span class="sampledata">9 8<br>
2 -6 3 5 1 -5 -3 6 3
GET-SUM 5 4
MAX-SUM
INSERT 8 3 -5 7 2
DELETE 12 1
MAKE-SAME 3 3 2
REVERSE 3 6
GET-SUM 5 4
MAX-SUM

Sample Output

        <div class="content"><span class="sampledata">-1<br>
10
1
10

留言