直接进行一个暴力的打
无法拿满分
但是70多行水一水就能拿到17/20的分数 何乐而不为捏qwq
#include <iostream>
#include <set>
using namespace std;
struct Node {
int l, r;
mutable int v;
Node(int _l, int _r = -1, int _v = 0) : l(_l), r(_r), v(_v) {}
bool operator< (const Node& other) const {
return l < other.l;
}
};
using iter = set<Node>::iterator;
set<Node> S;
int n, m;
iter split(int pos) {
iter it = S.lower_bound(Node(pos));
if (it != S.end() && it->l == pos) return it;
--it;
int l = it->l, r = it->r, v = it->v;
S.erase(it);
S.insert(Node(l, pos - 1, v));
return S.insert(Node(pos, r, v)).first;
}
void assign(int l, int r, int v) {
iter itr = split(r + 1), itl = split(l);
S.erase(itl, itr);
S.insert(Node(l, r, v));
}
int query(int l, int r) {
int cur = 0, res = 0;
iter itr = split(r + 1), itl = split(l);
for (; itl != itr; ++itl) {
if (!itl->v) cur += itl->r - itl->l + 1, res = max(res, cur);
else cur = 0;
}
return res;
}
void cure(int l1, int r1, int l2, int r2) {
iter itr = split(r1 + 1), itl = split(l1);
int cnt = 0;
for (; itl != itr; ++itl)
if (itl->v) cnt += itl->r - itl->l + 1;
assign(l1, r1, 0);
itr = split(r2 + 1), itl = split(l2);
for (; itl != itr && cnt; ++itl) {
int len = itl->r - itl->l + 1;
if (itl->v) continue;
if (len <= cnt) itl->v = 1, cnt -= len;
else assign(itl->l, itl->l + cnt - 1, 1), cnt = 0;
}
}
int main() {
scanf("%d%d", &n, &m);
S.insert(Node(1, n, 1));
while (m--) {
int op, a, b, c, d;
scanf("%d%d%d", &op, &a, &b);
if (op == 0) assign(a, b, 0);
if (op == 1) {
scanf("%d%d", &c, &d);
cure(a, b, c, d);
}
if (op == 2) printf("%d\n", query(a, b));
}
return 0;
}
线段树外二分 找到第一个c~pos的0的个数是cnt的位置
$O(nlog^2n)$的复杂度 不过足以通过
#include <iostream>
using namespace std;
const int N = 200010;
struct Node {
int l, r;
int ls, rs, ms;
int sum; // 坏块数量
int cov;
}tr[N << 2];
int n, m;
void pushup(Node &u, Node &l, Node &r) {
u.sum = l.sum + r.sum;
u.ls = l.ls;
if (l.ls == l.r - l.l + 1) u.ls += r.ls;
u.rs = r.rs;
if (r.rs == r.r - r.l + 1) u.rs += l.rs;
u.ms = max(max(l.ms, r.ms), l.rs + r.ls);
}
void pushup(int u) {
pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}
void build(int u, int l, int r) {
tr[u] = {l, r, 0, 0, 0, 0, -1};
if (l == r) return;
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
void assign(Node& u, int v) {
u.ls = u.rs = u.ms = u.sum = !v * (u.r - u.l + 1);
u.cov = v;
}
void pushdown(int u) {
if (~tr[u].cov) {
assign(tr[u << 1], tr[u].cov);
assign(tr[u << 1 | 1], tr[u].cov);
tr[u].cov = -1;
}
}
void modify(int u, int l, int r, int v) {
if (tr[u].cov == v) return;
if (tr[u].l >= l && tr[u].r <= r) {
assign(tr[u], v);
return;
}
int mid = tr[u].l + tr[u].r >> 1;
pushdown(u);
if (l <= mid) modify(u << 1, l, r, v);
if (r > mid) modify(u << 1 | 1, l, r, v);
pushup(u);
}
Node query(int u, int l, int r) {
if (tr[u].l >= l && tr[u].r <= r) return tr[u];
int mid = tr[u].l + tr[u].r >> 1;
pushdown(u);
if (r <= mid) return query(u << 1, l, r);
if (l > mid) return query(u << 1 | 1, l, r);
Node res, left = query(u << 1, l, r), right = query(u << 1 | 1, l, r);
pushup(res, left, right);
return res;
}
int main() {
scanf("%d%d", &n, &m);
build(1, 1, n);
while (m--) {
int op, a, b, c, d;
scanf("%d%d%d", &op, &a, &b);
if (op == 0) modify(1, a, b, 0);
if (op == 1) {
scanf("%d%d", &c, &d);
int cnt = b - a + 1 - query(1, a, b).sum;
if (!cnt) continue;
modify(1, a, b, 0);
if (query(1, c, d).sum <= cnt) modify(1, c, d, 1);
else {
int l = c, r = d;
while (l < r) {
int mid = l + r >> 1;
if (query(1, c, mid).sum > cnt) r = mid;
else l = mid + 1;
}
modify(1, c, l - 1, 1);
}
}
if (op == 2) printf("%d\n", query(1, a, b).ms);
}
return 0;
}
考虑树外二分转树内二分
$O(nlogn)$
#include <iostream>
using namespace std;
const int N = 200010;
struct Node {
int l, r;
int ls, rs, ms;
int sum; // 坏块数量
int cov;
}tr[N << 2];
int n, m;
void pushup(Node &u, Node &l, Node &r) {
u.sum = l.sum + r.sum;
u.ls = l.ls;
if (l.ls == l.r - l.l + 1) u.ls += r.ls;
u.rs = r.rs;
if (r.rs == r.r - r.l + 1) u.rs += l.rs;
u.ms = max(max(l.ms, r.ms), l.rs + r.ls);
}
void pushup(int u) {
pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}
void build(int u, int l, int r) {
tr[u] = {l, r, 0, 0, 0, 0, -1};
if (l == r) return;
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
void assign(Node& u, int v) {
u.ls = u.rs = u.ms = u.sum = !v * (u.r - u.l + 1);
u.cov = v;
}
void pushdown(int u) {
if (~tr[u].cov) {
assign(tr[u << 1], tr[u].cov);
assign(tr[u << 1 | 1], tr[u].cov);
tr[u].cov = -1;
}
}
void modify(int u, int l, int r, int v) {
if (tr[u].cov == v) return;
if (tr[u].l >= l && tr[u].r <= r) {
assign(tr[u], v);
return;
}
int mid = tr[u].l + tr[u].r >> 1;
pushdown(u);
if (l <= mid) modify(u << 1, l, r, v);
if (r > mid) modify(u << 1 | 1, l, r, v);
pushup(u);
}
Node query(int u, int l, int r) {
if (r < l) return {0, 0, 0, 0, 0, 0};
if (tr[u].l >= l && tr[u].r <= r) return tr[u];
int mid = tr[u].l + tr[u].r >> 1;
pushdown(u);
if (r <= mid) return query(u << 1, l, r);
if (l > mid) return query(u << 1 | 1, l, r);
Node res, left = query(u << 1, l, r), right = query(u << 1 | 1, l, r);
pushup(res, left, right);
return res;
}
int search(int u, int l, int r, int k) {
if (tr[u].l == tr[u].r) return tr[u].l;
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (r <= mid) return search(u << 1, l, r, k);
if (l > mid) return search(u << 1 | 1, l, r, k);
if (k <= tr[u << 1].sum) return search(u << 1, l, r, k);
return search(u << 1 | 1, l, r, k - tr[u << 1].sum);
}
int main() {
scanf("%d%d", &n, &m);
build(1, 1, n);
while (m--) {
int op, a, b, c, d;
scanf("%d%d%d", &op, &a, &b);
if (op == 0) modify(1, a, b, 0);
if (op == 1) {
scanf("%d%d", &c, &d);
int cnt = b - a + 1 - query(1, a, b).sum;
if (!cnt) continue;
modify(1, a, b, 0);
if (query(1, c, d).sum <= cnt) modify(1, c, d, 1);
else {
int pos = search(1, 1, n, query(1, 1, c - 1).sum + cnt);
modify(1, c, pos, 1);
}
}
if (op == 2) printf("%d\n", query(1, a, b).ms);
}
return 0;
}