大家好！我是老码农。
AC掉我也问了小码匠几个问题。
- 第1：为啥没想到要用二分处理找到一个区间，使得脑洞个数小于脑组织的个数？
- 回答的干净利索：没看出来单调递增
- 第2：调试的时候主要是哪卡住了？
- 回答的继续很直接：二分的边界
- 第3：你后来画了一张图，对调试有帮助吗？
- 没任何帮助。
- 第4：这道题卡部分分好卡吗？
- 20分比较容易，暴力枚举就行；
- 50分不太好卡过去；
划重点：作为一个局外人，线段树代码打起来还是有些难度的，而且调试起来比较费时间。
有时比赛还真不如直接先干个暴力，后面有精力在调试线段树。
别线段树没调出来，暴力分也没拿到。
[SHOI2015] 脑洞治疗仪
- https://www.luogu.com.cn/problem/P4344
- AC代码
#include <bits/stdc .h>
using namespace std;
const int maxn = 2e5 5;
struct line {
int l, r;
int sum, len, add, w, lmax, rmax, ans;
} t[4 * maxn];
void push_up(int u) {
t[u].sum = t[u << 1].sum t[u << 1 | 1].sum;
t[u].lmax = t[u << 1].lmax;
t[u].lmax = t[u << 1].lmax == t[u << 1].len ? t[u << 1 | 1].lmax : 0;
t[u].rmax = t[u << 1 | 1].rmax;
t[u].rmax = t[u << 1 | 1].rmax == t[u << 1 | 1].len ? t[u << 1].rmax : 0;
t[u].ans = max({t[u << 1].ans, t[u << 1 | 1].ans, t[u << 1].rmax t[u << 1 | 1].lmax});
}
void build(int u, int l, int r) {
t[u].l = l;
t[u].r = r;
t[u].len = r - l 1;
t[u].add = -1;
if (l == r) {
t[u].sum = 1;
t[u].lmax = 0;
t[u].rmax = 0;
t[u].ans = 0;
return;
}
int mid = (l r) >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid 1, r);
push_up(u);
}
void change(line &x, int len, int s, int add) {
x.ans = len;
x.lmax = len;
x.rmax = len;
x.sum = s;
x.add = add;
}
void push_down(int u) {
auto &root = t[u];
auto &left = t[u << 1];
auto &right = t[u << 1 | 1];
if (root.add == 0) {
change(left, left.len, 0, 0);
change(right, right.len, 0, 0);
} else if (root.add == 1) {
change(left, 0, left.len, 1);
change(right, 0, right.len, 1);
}
root.add = -1;
}
void modify(int u, int l, int r, int opt) {
if (t[u].l >= l && t[u].r <= r) {
opt == 0 ? change(t[u], t[u].len, 0, 0) : change(t[u], 0, t[u].len, 1);
} else {
push_down(u);
int mid = (t[u].l t[u].r) >> 1;
if (mid >= l) {
modify(u << 1, l, r, opt);
}
if (mid < r) {
modify(u << 1 | 1, l, r, opt);
}
push_up(u);
}
}
int query(int u, int l, int r, int opt) {
if (t[u].l >= l && t[u].r <= r) {
return opt == 1 ? t[u].sum : t[u].len - t[u].sum;
} else {
push_down(u);
int mid = (t[u].l t[u].r) >> 1;
int s = 0;
if (mid >= l) {
s = query(u << 1, l, r, opt);
}
if (mid < r) {
s = query(u << 1 | 1, l, r, opt);
}
return s;
}
}
void modify2(int l0, int r0, int l1, int r1) {
int x = query(1, l0, r0, 1);
if (x == 0) {
return;
}
modify(1, l0, r0, 0);
int l = l1;
int r = r1;
int ans;
while (l <= r) {
int mid = (l r) >> 1;
if (query(1, l1, mid, 0) <= x) {
l = mid 1;
ans = mid;
} else {
r = mid - 1;
}
}
modify(1, l1, ans, 1);
}
int query2(int u, int l, int r) {
if (t[u].l >= l && t[u].r <= r) {
return t[u].ans;
}
push_down(u);
int s = 0;
int mid = (t[u].l t[u].r) >> 1;
if (mid >= l) {
s = max(s, query2(u << 1, l, r));
}
if (mid < r) {
s = max(s, query2(u << 1 | 1, l, r));
}
return max(s, min(t[u << 1].rmax, t[u << 1 | 1].l - l) min(t[u << 1 | 1].lmax, r - t[u << 1].r));
}
void best_coder() {
int n, m;
cin >> n >> m;
build(1,1,n);
while(m--){
int opt;
cin >> opt;
if(opt == 0) {
int l, r;
cin >> l >> r;
modify(1, l, r, 0);
} else if (opt == 1) {
int l0, r0, l1, r1;
cin >> l0 >> r0 >> l1 >> r1;
modify2(l0, r0, l1, r1);
} else {
int l, r;
cin >> l >> r;
cout << query2(1, l, r) << 'n';
}
}
}
void happy_coder() {
}
int main() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// 小码匠
best_coder();
// 最优解
// happy_coder();
return 0;
}
总结
记得「关注」、点「赞」、点「在看」支持一下老码农，感谢大家的支持！
