目录

  1. 引言
  2. BZOJ 4592: [Shoi2015]脑洞治疗仪
    1. Description
    2. Input
    3. Output
    4. Sample Input
    5. Sample Output
    6. Source
    7. 题目分析
    8. 代码

引言

BZOJ 4592: [Shoi2015]脑洞治疗仪 题解

BZOJ 4592: [Shoi2015]脑洞治疗仪

  • Time Limit: 20 Sec

  • Memory Limit: 256 MB

Description

曾经发明了自动刷题机的发明家SHTSC又公开了他的新发明:脑洞治疗仪—一种可以治疗他因为发明而日益增大的脑洞的神秘装置。
为了简单起见,我们将大脑视作一个01序列。1代表这个位置的脑组织正常工作,0代表这是一块脑洞。
1 0 1 0 0 0 1 1 1 0
脑洞治疗仪修补某一块脑洞的基本工作原理就是将另一块连续区域挖出,将其中正常工作的脑组织填补在这块脑洞中。
(所以脑洞治疗仪是脑洞的治疗仪?)
例如,用上面第8号位置到第10号位置去修补第1号位置到第4号位置的脑洞。我们就会得到:
1 1 1 1 0 0 1 0 0 0
如果再用第1号位置到第4号位置去修补第8号位置到第10号位置:
0 0 0 0 0 0 1 1 1 1
这是因为脑洞治疗仪会把多余出来的脑组织直接扔掉。
如果再用第7号位置到第10号位置去填补第1号位置到第6号位置:
1 1 1 1 0 0 0 0 0 0
这是因为如果新脑洞挖出来的脑组织不够多,脑洞治疗仪仅会尽量填补位置比较靠前的脑洞。
假定初始时SHTSC并没有脑洞,给出一些挖脑洞和脑洞治疗的操作序列,你需要即时回答SHTSC的问题:
在大脑某个区间中最大的连续脑洞区域有多大。

Input

第一行两个整数n,m。表示SHTSC的大脑可分为从1到n编号的n个连续区域。有m个操作。
以下m行每行是下列三种格式之一。
0 l r :SHTSC挖了一个从l到r的脑洞。
1 l0 r0 l1 r2 :SHTSC进行了一次脑洞治疗,用从l0到r0的脑组织修补l1到r1的脑洞。
2 l r :SHTSC询问l到r这段区间最大的脑洞有多大。
n,m <=200000,1<=l<=r<=n

Output

对于每个询问,输出一行一个整数,表示询问区间内最大连续脑洞区域有多大。

Sample Input

10 10

0 2 2

0 4 6

0 10 10

2 1 10

1 8 10 1 4

2 1 10

1 1 4 8 10

2 1 10

1 7 10 1 6

2 1 10

Sample Output

3

3

6

6

Source

By 佚名上传

题目分析

线段树

我们发现,需要维护01序列的最长连续段,这部分使用经典的前中后法即可维护

然后我们还需要维护区间1的个数,即区间和,直接搞就好

对于最后一个填充操作,用区间覆盖实现,我们优先搞左边,如果左边搞完还剩下脑组织,就搞右边,如此即可

还可以结合区间和以及区间覆盖标记搞一些小的优化剪枝,比如如果已经全是1就直接跳出等等

所以还算是比较快的,rank7

还是1A,挺开心

代码

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
/**************************************************************
Problem: 4592
User: Renatus
Language: C++
Result: Accepted
Time:2932 ms
Memory:16840 kb
****************************************************************/
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cassert>
#define maxn 400005
#define rep(i, l, r) for (register int i = l; i <= r; i++)
#define per(i, r, l) for (register int i = r; i >= l; i--)
#define gc() ((p1 == p2 && (p2 = (p1 = buffer) + fread(buffer, 1, maxn, stdin), p1 == p2)) ? EOF : *p1++)
using namespace std;
char *p1, *p2;
char buffer[maxn];
template <class T> void read(T& x){
char ch = gc(); x = 0; bool f = 1;
while (!('0' <= ch && ch <= '9') && ch != '-') ch = gc();
if (ch == '-') f = 0, ch = gc();
while ('0' <= ch && ch <= '9') x = (x << 1) + (x << 3) + ch - '0', ch = gc();
if (!f) x = -x;
}
int n, m;
int set[maxn << 1];
int le[maxn << 1];
int ri[maxn << 1];
int mi[maxn << 1];
int sum[maxn << 1];
int qx, qy, qd;
void pushup(int l, int r, int o){
int mid = ((r - l) >> 1) + l;
if (!sum[o << 1]) le[o] = mid - l + 1 + le[o << 1 | 1];
else le[o] = le[o << 1];
if (!sum[o << 1 | 1]) ri[o] = r - mid + ri[o << 1];
else ri[o] = ri[o << 1 | 1];
mi[o] = max(ri[o << 1] + le[o << 1 | 1], max(mi[o << 1], mi[o << 1 | 1]));
sum[o] = sum[o << 1] + sum[o << 1 | 1];
}
void pushdown(int l, int r, int o){
if (set[o] == -1 || l == r) return;
if (set[o]){
int mid = ((r - l) >> 1) + l;
int ls = o << 1;
le[ls] = ri[ls] = mi[ls] = 0, sum[ls] = mid - l + 1;
set[ls] = 1;
int rs = o << 1 | 1;
le[rs] = ri[rs] = mi[rs] = 0, sum[rs] = r - mid;
set[rs] = 1;
}
else{
int mid = ((r - l) >> 1) + l;
int ls = o << 1;
le[ls] = ri[ls] = mi[ls] = mid - l + 1, sum[ls] = 0;
set[ls] = 0;
int rs = o << 1 | 1;
le[rs] = ri[rs] = mi[rs] = r - mid, sum[rs] = 0;
set[rs] = 0;
}
set[o] = -1;
}
void init(int l, int r, int o){
set[o] = -1;
if (l == r) {sum[o] = 1; return;}
int mid = ((r - l) >> 1) + l;
init(l, mid, o << 1);
init(mid + 1, r, o << 1 | 1);
sum[o] = sum[o << 1] + sum[o << 1 | 1];
}
int get(int l, int r, int o){
if (set[o] == 0) return 0;
if (set[o] == 1) return min(qy, r) - max(qx, l) + 1;
pushdown(l, r, o);
if (qx <= l && r <= qy) return sum[o];
int mid = ((r - l) >> 1) + l, ans = 0;
if (qx <= mid) ans += get(l, mid, o << 1);
if (qy > mid) ans += get(mid + 1, r, o << 1 | 1);
return ans;
}
void dig(int l, int r, int o){
if (set[o] == 0) return;
pushdown(l, r, o);
if (qx <= l && r <= qy) {
set[o] = sum[o] = 0;
le[o] = ri[o] = mi[o] = r - l + 1;
return;
}
int mid = ((r - l) >> 1) + l;
if (qx <= mid) dig(l, mid, o << 1);
if (qy > mid) dig(mid + 1, r, o << 1 | 1);
pushup(l, r, o);
}
void fill(int l, int r, int o){
if (set[o] == 1 || !qd) return;
pushdown(l, r, o);
if (qx <= l && r <= qy){
int rest = r - l + 1 - sum[o];
if (rest <= qd){
qd -= rest;
set[o] = 1;
le[o] = ri[o] = mi[o] = 0;
sum[o] = r - l + 1;
}
else{
int mid = ((r - l) >> 1) + l;
fill(l, mid, o << 1);
if (qd) fill(mid + 1, r, o << 1 | 1);
pushup(l, r, o);
}
return;
}
int mid = ((r - l) >> 1) + l;
if (qx <= mid && qd) fill(l, mid, o << 1);
if (qy > mid && qd) fill(mid + 1, r, o << 1 | 1);
pushup(l, r, o);
}
struct ele{
int x, y, m;
ele(int x = 0, int y = 0, int m = 0) : x(x), y(y), m(m){}
bool operator = (const ele b) {
x = b.x, y = b.y, m = b.m;
}
};
ele query(int l, int r, int o){
pushdown(l, r, o);
if (qx <= l && r <= qy) return ele(le[o], ri[o], mi[o]);
int mid = ((r - l) >> 1) + l;
ele ans1 = ele(-1, -1, -1), ans2 = ele(-1, -1, -1), ans = ele(-1, -1, -1);
if (qx <= mid) ans1 = query(l, mid, o << 1);
if (qy > mid) ans2 = query(mid + 1, r, o << 1 | 1);
if (ans1.x == -1) return ans2;
if (ans2.x == -1) return ans1;
if (ans1.x == mid - l + 1) ans.x = ans1.x + ans2.x;
else ans.x = ans1.x;
if (ans2.y == r - mid) ans.y = ans1.y + ans2.y;
else ans.y = ans2.y;
ans.m = max(ans1.y + ans2.x, max(ans1.m, ans2.m));
return ans;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("cure.in", "r", stdin);
#endif
int op;
read(n), read(m);
init(1, n, 1);
rep(i, 1, m){
read(op);
switch(op){
case 0: read(qx), read(qy), dig(1, n, 1); break;
case 1: read(qx), read(qy), qd = get(1, n, 1), dig(1, n, 1), read(qx), read(qy), fill(1, n, 1); break;
case 2: read(qx), read(qy); ele ans = query(1, n, 1); printf("%d\n", max(ans.x, max(ans.y, ans.m))); break;
}
}
return 0;
}