题面
事情是这样的，看到标签是线段树，就果断手搓了一个线段树。
可我学艺不精，那个代码只过了 Subtask #1 ，WA0代码如下：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 1e5 + 10;
struct SegmentTree {
int l, r;
int sum;
int lmax, rmax, mmax;
int lazy;
} tree[maxn << 2];
int a[maxn];
void push_up(int rt) {
tree[rt].sum = tree[rt << 1].sum + tree[rt << 1 | 1].sum;
tree[rt].lmax = max(tree[rt << 1].lmax, tree[rt << 1].sum + tree[rt << 1 | 1].lmax);
tree[rt].rmax = max(tree[rt << 1 | 1].rmax, tree[rt << 1 | 1].sum + tree[rt << 1].rmax);
tree[rt].mmax = max(tree[rt << 1].rmax + tree[rt << 1 | 1].lmax, max(tree[rt << 1].mmax, tree[rt << 1 | 1].mmax));
}
void build(int rt, int l, int r) {
tree[rt].l = l;
tree[rt].r = r;
tree[rt].lazy = -1;
if (l == r) {
tree[rt].sum = a[l];
tree[rt].lmax = a[l];
tree[rt].rmax = a[l];
tree[rt].mmax = a[l];
return;
}
int mid = (l + r) >> 1;
build(rt << 1, l, mid);
build(rt << 1 | 1, mid + 1, r);
push_up(rt);
}
void push_down(int rt) {
if (tree[rt].lazy!= -1) {
int lazy = tree[rt].lazy;
tree[rt << 1].lazy = lazy;
tree[rt << 1 | 1].lazy = lazy;
if (lazy == 0) {
tree[rt << 1].sum = 0;
tree[rt << 1].lmax = 0;
tree[rt << 1].rmax = 0;
tree[rt << 1].mmax = 0;
tree[rt << 1 | 1].sum = 0;
tree[rt << 1 | 1].lmax = 0;
tree[rt << 1 | 1].rmax = 0;
tree[rt << 1 | 1].mmax = 0;
} else if (lazy == 1) {
tree[rt << 1].sum = tree[rt << 1].r - tree[rt << 1].l + 1;
tree[rt << 1].lmax = tree[rt << 1].r - tree[rt << 1].l + 1;
tree[rt << 1].rmax = tree[rt << 1].r - tree[rt << 1].l + 1;
tree[rt << 1].mmax = tree[rt << 1].r - tree[rt << 1].l + 1;
tree[rt << 1 | 1].sum = tree[rt << 1 | 1].r - tree[rt << 1 | 1].l + 1;
tree[rt << 1 | 1].lmax = tree[rt << 1 | 1].r - tree[rt << 1 | 1].l + 1;
tree[rt << 1 | 1].rmax = tree[rt << 1 | 1].r - tree[rt << 1 | 1].l + 1;
tree[rt << 1 | 1].mmax = tree[rt << 1 | 1].r - tree[rt << 1 | 1].l + 1;
} else {
tree[rt << 1].sum = tree[rt << 1].r - tree[rt << 1].l + 1 - tree[rt << 1].sum;
swap(tree[rt << 1].lmax, tree[rt << 1].rmax);
tree[rt << 1].lmax = tree[rt << 1].r - tree[rt << 1].l + 1 - tree[rt << 1].lmax;
tree[rt << 1].rmax = tree[rt << 1].r - tree[rt << 1].l + 1 - tree[rt << 1].rmax;
tree[rt << 1].mmax = tree[rt << 1].r - tree[rt << 1].l + 1 - tree[rt << 1].mmax;
tree[rt << 1 | 1].sum = tree[rt << 1 | 1].r - tree[rt << 1 | 1].l + 1 - tree[rt << 1 | 1].sum;
swap(tree[rt << 1 | 1].lmax, tree[rt << 1 | 1].rmax);
tree[rt << 1 | 1].lmax = tree[rt << 1 | 1].r - tree[rt << 1 | 1].l + 1 - tree[rt << 1 | 1].lmax;
tree[rt << 1 | 1].rmax = tree[rt << 1 | 1].r - tree[rt << 1 | 1].l + 1 - tree[rt << 1 | 1].rmax;
tree[rt << 1 | 1].mmax = tree[rt << 1 | 1].r - tree[rt << 1 | 1].l + 1 - tree[rt << 1 | 1].mmax;
}
tree[rt].lazy = -1;
}
}
void update(int rt, int l, int r, int val) {
if (l <= tree[rt].l && tree[rt].r <= r) {
if (val == 0) {
tree[rt].sum = 0;
tree[rt].lmax = 0;
tree[rt].rmax = 0;
tree[rt].mmax = 0;
tree[rt].lazy = 0;
} else if (val == 1) {
tree[rt].sum = tree[rt].r - tree[rt].l + 1;
tree[rt].lmax = tree[rt].r - tree[rt].l + 1;
tree[rt].rmax = tree[rt].r - tree[rt].l + 1;
tree[rt].mmax = tree[rt].r - tree[rt].l + 1;
tree[rt].lazy = 1;
} else {
tree[rt].sum = tree[rt].r - tree[rt].l + 1 - tree[rt].sum;
swap(tree[rt].lmax, tree[rt].rmax);
tree[rt].lmax = tree[rt].r - tree[rt].l + 1 - tree[rt].lmax;
tree[rt].rmax = tree[rt].r - tree[rt].l + 1 - tree[rt].rmax;
tree[rt].mmax = tree[rt].r - tree[rt].l + 1 - tree[rt].mmax;
tree[rt].lazy = 2;
}
return;
}
push_down(rt);
int mid = (tree[rt].l + tree[rt].r) >> 1;
if (l <= mid) update(rt << 1, l, r, val);
if (r > mid) update(rt << 1 | 1, l, r, val);
push_up(rt);
}
int query_sum(int rt, int l, int r) {
if (l <= tree[rt].l && tree[rt].r <= r) {
return tree[rt].sum;
}
push_down(rt);
int mid = (tree[rt].l + tree[rt].r) >> 1;
int ans = 0;
if (l <= mid) ans += query_sum(rt << 1, l, r);
if (r > mid) ans += query_sum(rt << 1 | 1, l, r);
return ans;
}
int query_max(int rt, int l, int r) {
if (l <= tree[rt].l && tree[rt].r <= r) {
return tree[rt].mmax;
}
push_down(rt);
int mid = (tree[rt].l + tree[rt].r) >> 1;
if (r <= mid) return query_max(rt << 1, l, r);
else if (l > mid) return query_max(rt << 1 | 1, l, r);
else {
int leftmax = query_max(rt << 1, l, mid);
int rightmax = query_max(rt << 1 | 1, mid + 1, r);
int crossmax = min(mid - l + 1, tree[rt << 1].rmax) + min(r - mid, tree[rt << 1 | 1].lmax);
return max(crossmax, max(leftmax, rightmax));
}
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
build(1, 0, n - 1);
for (int i = 0; i < m; i++) {
int op, l, r;
scanf("%d%d%d", &op, &l, &r);
if (op == 0) {
update(1, l, r, 0);
} else if (op == 1) {
update(1, l, r, 1);
} else if (op == 2) {
update(1, l, r, 2);
} else if (op == 3) {
printf("%d\n", query_sum(1, l, r));
} else if (op == 4) {
printf("%d\n", query_max(1, l, r));
}
}
return 0;
}
我意识到应该是 query_max 写错了，但是蒟蒻不会改。。。暴力了一下，《WA100》：
#include <bits/stdc++.h>
using namespace std;
int main(void)
{
int n, m;
cin >> n >> m;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
while (m--) {
int ch, l, r;
cin >> ch >> l >> r;
if (ch == 0) {
for (int i = l; i <= r; i++) {
a[i] = 0;
}
} else if (ch == 1) {
for (int i = l; i <= r; i++) {
a[i] = 1;
}
} else if (ch == 2) {
for (int i = l; i <= r; i++) {
a[i] ^= 1;
}
} else if (ch == 3) {
int cnt = 0;
for (int i = l; i <= r; i++) {
if (a[i] == 1) {
cnt++;
}
}
cout << cnt << '\n';
} else if (ch == 4) {
int ans = 0;
int cnt = 0;
for (int i = l; i <= r; i++) {
if (a[i] == 1) {
cnt++;
} else {
cnt = 0;
}
ans = max(ans, cnt);
}
cout << ans << '\n';
}
}
return 0;
}
数据过水。我除了 Subtask #1 其他都过了，于是开始尝试两个代码融合，在我的骗分大法的加持下，我过了？。太水了吧。。。