大家好！我是老码农。
今天备受折磨的小码匠，终于在早晨AC掉了一道线段树题。
话说这道题，从周三晚上开始，代码写了7、8成；
然后周四继续调试，无果，0分，只过了Subtask #1这个点；
然后周五继续发力，继续无果，依然是0分，依然是只过了Subtask #1这个点；
今天早晨小码匠不甘心，写了会作业，继续搞这道题，终于在11点29分AC掉了这道题；
这道题也是最近做的比较吃力的一道题；
耗时：周三1.5小时 周四1.5小时 周五1.5小时 周六1.5小时 = 6小时啊。
做完题后跟小码匠交流，感觉收获还是很多，对线段树理解比之前上了一个小层次。
这道题也是最近写的代码最长的，后面虐心的题目会越来越多。
爽歪歪的题目实则对自己帮助不是很大。
贴上代码，留个纪念。
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
constexpr int MAX_NUM = 1e5 5;
struct line {
int l, r, len, sum, max_zero, max_one, left_zero, right_zero, left_one, right_one;
int lazy, add;
} t[8 * MAX_NUM];
int a[MAX_NUM];
void push_up(int u) {
auto &root = t[u];
auto &left = t[u << 1];
auto &right = t[u << 1 | 1];
if (left.left_zero == left.len) {
root.left_zero = left.left_zero right.left_zero;
} else {
root.left_zero = left.left_zero;
}
if (left.left_one == left.len) {
root.left_one = left.left_one right.left_one;
} else {
root.left_one = left.left_one;
}
if (right.right_zero == right.len) {
root.right_zero = right.right_zero left.right_zero;
} else {
root.right_zero = right.right_zero;
}
if (right.right_one == right.len) {
root.right_one = right.right_one left.right_one;
} else {
root.right_one = right.right_one;
}
root.max_zero = max({left.max_zero, right.max_zero,
left.right_zero right.left_zero});
root.max_one = max({left.max_one, right.max_one,
left.right_one right.left_one});
root.sum = left.sum right.sum;
}
void build(int u, int l, int r) {
t[u].l = l;
t[u].r = r;
t[u].len = r - l 1;
t[u].lazy = -1;
if (l == r) {
t[u].left_zero = 1 - a[l];
t[u].left_one = a[l];
t[u].right_zero = 1 - a[l];
t[u].right_one = a[l];
t[u].max_zero = 1 - a[l];
t[u].max_one = a[l];
t[u].sum = a[l];
return;
} else {
int mid = (l r) >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid 1 , r);
push_up(u);
}
}
void change(line &x, bool flag) {
x.sum = 0;
x.left_one = 0;
x.right_one = 0;
x.left_zero = x.len;
x.right_zero = x.len;
x.max_zero = x.len;
x.max_one = 0;
if(flag) {
swap(x.left_one, x.left_zero);
swap(x.right_one, x.right_zero);
swap(x.max_one, x.max_zero);
x.sum = x.len;
}
}
void change2(line &x) {
swap(x.left_one, x.left_zero);
swap(x.right_one, x.right_zero);
swap(x.max_one, x.max_zero);
x.sum = x.len - x.sum;
}
void push_down(int u) {
auto &root = t[u];
auto &left = t[u << 1];
auto &right = t[u << 1 | 1];
if (root.lazy == 0) {
change(left, false);
change(right, false);
} else if (root.lazy == 1) {
change(left, true);
change(right, true);
}
if (root.lazy != -1) {
root.add = 0;
left.lazy = root.lazy;
right.lazy = root.lazy;
left.add = 0;
right.add = 0;
}
if (root.add == 1) {
root.add = 0;
if (left.lazy != -1) {
left.lazy ^= 1;
} else {
left.add ^= 1;
}
if (right.lazy != -1) {
right.lazy ^= 1;
} else {
right.add ^= 1;
}
change2(left);
change2(right);
}
root.lazy = -1;
}
void modify(int u, int l, int r, int opt) {
push_down(u);
if (t[u].l >= l && t[u].r <= r) {
if (opt == 1) {
change(t[u], false);
t[u].lazy = 0;
} else if (opt == 2) {
change(t[u], true);
t[u].lazy = 1;
} else if(opt == 3) {
change2(t[u]);
t[u].add ^= 1;
}
return;
} else {
int mid = (t[u].l t[u].r) >> 1;
if (l <= mid) {
modify(u << 1, l, r, opt);
}
if (r > mid) {
modify(u << 1 | 1, l, r, opt);
}
push_up(u);
}
}
int query(int u, int l, int r) {
if (t[u].l >= l && t[u].r <= r) {
return t[u].sum;
}
push_down(u);
int mid = (t[u].l t[u].r) >> 1;
int s = 0;
if (l <= mid) {
s = query(u << 1, l, r);
}
if (r > mid) {
s = query(u << 1 | 1, l, r);
}
return s;
}
//line p, q, ans;
line cnt(int u, int l, int r) {
if (t[u].l >= l && t[u].r <= r) {
return t[u];
} else {
push_down(u);
int mid = (t[u].l t[u].r) >> 1;
line p = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
line q = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
line ans = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
if (l <= mid) {
p = cnt(u << 1, l, r);
ans.max_one = p.max_one;
}
if (r > mid) {
q = cnt(u << 1 | 1, l, r);
ans.max_one = max(ans.max_one, q.max_one);
}
ans.max_one = max(p.right_one q.left_one, ans.max_one);
if (p.left_one == p.len) {
ans.left_one = p.left_one q.left_one;
} else {
ans.left_one = p.left_one;
}
if (q.right_one == q.len) {
ans.right_one = p.right_one q.right_one;
} else {
ans.right_one = q.right_one;
}
return ans;
}
}
void best_coder() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i) {
cin >> a[i];
}
build(1,1,n);
for (int i = 0; i < m; i) {
int opt, l, r;
cin >> opt >> l >> r;
opt;
l;
r;
if(opt <= 3){
modify(1, l, r, opt);
} else if (opt == 4) {
cout << query(1, l, r) << 'n';
} else {
cout << cnt(1, l, r).max_one << '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;
}
总结
记得「关注」、点「赞」、点「在看」支持一下老码农，感谢大家的支持！
