[SHOI2015]脑洞治疗仪|最大连续子段+二分

码的我心力憔悴……我果然好菜啊QWQ

[SHOI2015]脑洞治疗仪

题目描述

曾经发明了自动刷题机的发明家 SHTSC 又公开了他的新发明:脑洞治疗仪——一种可以治疗他因为发明而日益增大的脑洞的神秘装置。

为了简单起见,我们将大脑视作一个 01 序列。1代表这个位置的脑组织正常工作,0代表这是一块脑洞。

1
1      0      1      0      0      0      1      1      1      0

脑洞治疗仪修补某一块脑洞的基本工作原理就是将另一块连续区域挖出,将其中正常工作的脑组织填补在这块脑洞中。(所以脑洞治疗仪是脑洞的治疗仪?)

例如,用上面第8号位置到第10号位置去修补第1号位置到第4号位置的脑洞,我们就会得到:

1
1      1      1      1      0      0      1      0      0      0

如果再用第1号位置到第4号位置去修补第8号位置到第10号位置:

1
0      0      0      0      0      0      1      1      1      1

这是因为脑洞治疗仪会把多余出来的脑组织直接扔掉。

如果再用第7号位置到第10号位置去填补第1号位置到第6号位置:

1
1      1      1      1      0      0      0      0      0      0

这是因为如果新脑洞挖出来的脑组织不够多,脑洞治疗仪仅会尽量填补位置比较靠前的脑洞。

假定初始时 SHTSC 并没有脑洞,给出一些挖脑洞和脑洞治疗的操作序列,你需要即时回答 SHTSC 的问题:在大脑某个区间中最大的连续脑洞区域有多大。

输入输出格式

输入格式:

第一行两个整数 n、m,表示 SHTSC 的大脑可分为从1到n编号的n个连续区域,有m个操作。

以下m行每行是下列三种格式之一:

  • $0lr$:SHTSC 挖了一个范围为$[l,r]$的脑洞。
  • $1l_0r_0l_1r_1$:SHTSC 进行了一次脑洞治疗,用从$l_0$到$r_0$的脑组织修补$l_1$到$r_1$的脑洞。
  • $2lr$:SHTSC 询问$[l,r]$区间内最大的脑洞有多大。

上述区间均在$[1,n]$范围内。

输出格式:

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

输入输出样例

输入样例#1:

1
2
3
4
5
6
7
8
9
10
11
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

输出样例#1:

1
3 3 6 6

说明

对于20%的数据,$n,m≤100$; 对于50%的数据,$n,m≤20000$; 对于100%的数据,$n,m≤200000$。


首先可以看出……这是一道线段数维护最大连续子段的题目(虽然我写了暴力区间修改)。

最大连续子段好像有更巧妙的做法……不过我不会。我就说说这题暴力怎么做。

首先操作0:区间修改。穿个标记。

操作1:简化一下就是,(1)查询$l_0$到$r_0$中1的个数$num$,将$l_0$到$r_0$覆盖为0。(2)在$l_1$到$r_1$中从前向后在0处填1,最多填$num$个数&&最多将$l_1$到$r_1$填满。

(1)比较好想,就是一个区间求和加上区间修改。

(2)因为是从前向后填,我们可以联想到用二分查找到当前可以填满的区间的位置。

直接讲不太好理解……还是看大佬的题解叭

%%%%%%%%%%%%%%%%%%%%%%%%%%%%

注意二分时起点要保证是0,如果当前起点是1的话,我们可以巧妙的转化一下,变成查询以当前起点开始的最长的连续为1的子段,这样查询到的位置的后一位就一定是当前区间最靠前的那个0。一直补到不能补为止。

操作2:查询最大连续子段

类似于操作1二分一下就好了(雾

这题为什么又有珂朵莉树(ODT)的题解啊

(话说不应该叫Old Driver Tree老司机树 老驱动树的嘛)

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
// luogu-judger-enable-o2
#include <cstring>
#include <cstdlib>
#include <cfloat>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cctype>
#include <map>
#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
#define ls (u << 1)
#define rs (u << 1 | 1)
using namespace std;

const int MAXN = 200010;
int n, m;

template <typename _Tp>
inline void read(_Tp &x) {
char ch = getchar( ); bool f = 0; x = 0;
while (!isdigit(ch)) { if (ch == '-') f = 1; ch = getchar( ); }
while (isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar( ); }
x = f ? -x : x;
}

struct Tree {
int l, r, siz, tag, sum;
}t[MAXN << 2];

void PushUp(int u) { t[u].sum = t[ls].sum + t[rs].sum; }

void Build(int u, int l, int r) {
t[u].l = l, t[u].r = r, t[u].siz = r - l + 1;
if (l == r) {
t[u].sum = 1;
return ;
}
int mid = (l + r) >> 1;
Build(ls, l, mid);
Build(rs, mid + 1, r);
PushUp(u);
}

void PushDown(int u) {
if (t[u].tag == -1) return ;
t[ls].sum = t[u].tag * t[ls].siz;
t[rs].sum = t[u].tag * t[rs].siz;
t[ls].tag = t[u].tag;
t[rs].tag = t[u].tag;
t[u].tag = -1;
}

void UpDate(int u, int x, int y, int k) {
if (t[u].l > y || x > t[u].r) return;
if (x <= t[u].l && t[u].r <= y) {
t[u].tag = k;
t[u].sum = k * t[u].siz;
return ;
}
PushDown(u);
int mid = (t[u].l + t[u].r) >> 1;
if (x <= mid) UpDate(ls, x, y, k);
if (y > mid) UpDate(rs, x, y, k);
PushUp(u);
}

int Query(int u, int x, int y) {
if (t[u].l > y || x > t[u].r) return 0;
if (x <= t[u].l && t[u].r <= y) return t[u].sum;
PushDown(u);
int mid = (t[u].l + t[u].r) >> 1, ans = 0;
if (x <= mid) ans += Query(ls, x, y);
if (y > mid) ans += Query(rs, x, y);
return ans;
}

int BinarySearch(int x, int y, int k) {
int l = 0, r = y - x, mid, tmp, ans;
if (x > y) return -1;
while (l <= r) {
mid = (l + r) >> 1;
tmp = Query(1, x, x + mid);
if (tmp == k * (mid + 1)) l = mid + 1;
else r = mid - 1;
}
return l;
}

int main( ) {
read(n), read(m);
Build(1, 1, n);
for (int i = 1; i <= (n << 2); ++ i) t[i].tag = -1;
int opt, l0, r0, l, r;
for (int i = 1; i <= m; ++ i) {
read(opt);
if (opt == 0) {
read(l), read(r);
UpDate(1, l, r, 0);
}
else if (opt == 1) {
read(l0), read(r0), read(l), read(r);
int tmp, num = Query(1, l0, r0), p = 0;
UpDate(1, l0, r0, 0);
/*-------------------神仙优化--------------------*/
if (num >= (r - l + 1) - Query(1, l, r)) {
UpDate(1, l, r, 1);
continue;
}
if (num == 0) continue;
/*-----------------------------------------------*/
while (1) {
tmp = Query(1, l, l);
if (tmp == 1) p = BinarySearch(l, r, 1), l += p;
p = BinarySearch(l, r, 0);
if (p == -1) break;
if (p > num) {
UpDate(1, l, l + num - 1, 1);
break;
}
else {
UpDate(1, l, l + p - 1, 1);
num -= p, l += p;
}
}
}
else if (opt == 2) {
read(l), read(r);
int tmp, ans = 0, p = 0;
while (1) {
tmp = Query(1, l, l);
if (tmp == 1) p = BinarySearch(l, r, 1), l += p;
p = BinarySearch(l, r, 0);
if (p == -1) break;
ans = max(ans, p);
l += p;
if (l > r) break;
}
printf("%d\n", ans);
}
}
return 0;
}

人丑常数大……开了O2勉强过了90分。剩下两个点要优化一下才能过。

哦对了这题tag的传递也有坑。

后续有可能会补上更优做法(咕咕咕)(不是ODT。这辈子都不可能写ODT的)

{% if theme.fireworks %} {% endif %} {{ live2d() }}