【题目描述】
曾经发明了自动刷题机的发明家 SHTSC 又公开了他的新发明：脑洞治疗仪——一种可以治疗他因为发明而日益增大的脑洞的神秘装置。
为了简单起见，我们将大脑视作一个 (01) 序列。(1) 代表这个位置的脑组织正常工作，(0) 代表这是一块脑洞。
| 1 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 0 |
例如，用上面第 (8) 号位置到第 (10) 号位置去修补第 (1) 号位置到第 (4) 号位置的脑洞，我们就会得到：
| 1 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
如果再用第 (7) 号位置到第 (10) 号位置去填补第 (1) 号位置到第 (6) 号位置：
| 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
假定初始时 SHTSC 并没有脑洞，给出一些挖脑洞和脑洞治疗的操作序列，你需要即时回答 SHTSC 的问题：在大脑某个区间中最大的连续脑洞区域有多大。
【输入格式】
第一行两个整数 (n)、(m)，表示 SHTSC 的大脑可分为从 (1) 到 (n) 编号的 (n) 个连续区域，有 (m) 个操作。
以下 (m) 行每行是下列三种格式之一：
- $0quad lquad r$：SHTSC 挖了一个范围为 $[l, r]$ 的脑洞。
- $1quad l_0quad r_0quad l_1quad r_1$：SHTSC 进行了一次脑洞治疗，用从 $l_0$ 到 $r_0$ 的脑组织修补 $l_1$ 到 $r_1$ 的脑洞。
- $2quad lquad r$：SHTSC 询问 $[l, r]$ 区间内最大的脑洞有多大。
【输出格式】
对于每个询问，输出一行一个整数，表示询问区间内最大连续脑洞区域有多大。
其实就是个板子题。。。
可以先看看Luogu SP1043
以上面这题为例，对于这种询问 “哪段区间是最...的”(哪段区间和最大) ，一般思路是线段树的每个节点([l,r])维护和最大的前缀([l,x])，后缀([y,r])在哪里。
然后父亲节点的前缀最大就是 MAX(左儿子最大的前缀和，左儿子整段区间的和+右儿子最大前缀和) 后缀同理 正确性显然。
这道题也是类似的，父亲节点的前缀最大就是 (左儿子整个区间都是0 ？ 左儿子整个区间+右儿子前缀0数量 : 左儿子前缀0数量) 后缀同理。
然后再维护一下区间和来进行修补操作就完了。。。
提一下怎么进行填1的操作
伪代码：
int update () {
如果 (整段区间在填补范围([x,y])内 && 剩下的可用1数量足以填满当前区间的0) {
打上懒标记;
return 可用1数量-填满当前区间需要的1数量;
}
pushdown();
可用1数量 = update(左儿子);//优先左儿子
可用1数量 = update(右儿子);
return 可用1数量
}
经证明，这个的时间复杂度依然是(O(log n))的 蒟蒻并不会证
总时间复杂度(O((n+m)log n))
【代码】
#include <bits/stdc++.h>
#define lson ind<<1
#define rson ind<<1|1
using namespace std;
inline int read() {
int x = 0, f = 1; char ch = getchar();
for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') f = -1;
for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ '0');
return x * f;
}
int n, m, tp, l0, r0, l1, r1;
struct segtree{
int l, r, tot, pre, suf, tag, mx;
} tr[2000005];
inline void add(int ind, int x) {
tr[ind].tag = x;
if (x == 0) {
tr[ind].tot = 0; tr[ind].pre = tr[ind].suf = tr[ind].mx = (tr[ind].r - tr[ind].l + 1);
} else {
tr[ind].tot = (tr[ind].r - tr[ind].l + 1); tr[ind].pre = tr[ind].suf = tr[ind].mx = 0;
}
}
inline void pushup(int ind) {
tr[ind].tot = tr[lson].tot + tr[rson].tot;
tr[ind].pre = tr[lson].pre; tr[ind].suf = tr[rson].suf;
if (tr[lson].pre == tr[lson].r - tr[lson].l + 1) tr[ind].pre += tr[rson].pre;
if (tr[rson].suf == tr[rson].r - tr[rson].l + 1) tr[ind].suf += tr[lson].suf;
tr[ind].mx = max(max(tr[lson].mx, tr[rson].mx), tr[lson].suf + tr[rson].pre);
}
void build(int ind, int l, int r) {
tr[ind].l = l; tr[ind].r = r; tr[ind].tag = -1;
if (l == r) {
tr[ind].tot = 1;
return;
}
int mid = (l + r) >> 1;
build(lson, l, mid); build(rson, mid+1, r);
pushup(ind);
}
inline void pushdown(int ind) {
if (tr[ind].tag == 0) {
add(lson, 0); add(rson, 0);
} else if (tr[ind].tag == 1) {
add(lson, 1); add(rson, 1);
}
tr[ind].tag = -1;
}
void update1(int ind, int x, int y) {
int l = tr[ind].l, r = tr[ind].r;
if (x <= l && r <= y) {
add(ind, 0);
return;
}
int mid = (l + r) >> 1;
pushdown(ind);
if (x <= mid) update1(lson, x, y);
if (mid < y) update1(rson, x, y);
pushup(ind);
}
int update2(int ind, int x, int y, int num) {
if (!num) return 0;
int l = tr[ind].l, r = tr[ind].r;
if (x <= l && r <= y && num >= r-l+1-tr[ind].tot) {
int ret = num-(r-l+1-tr[ind].tot);
add(ind, 1);
return ret;
}
int mid = (l + r) >> 1;
pushdown(ind);
if (x <= mid) num = update2(lson, x, y, num);
if (mid < y) num = update2(rson, x, y, num);
pushup(ind);
return num;
}
int query1(int ind, int x, int y) {
int l = tr[ind].l, r = tr[ind].r;
if (x <= l && r <= y) {
return tr[ind].tot;
}
int mid = (l + r) >> 1, ret = 0;
pushdown(ind);
if (x <= mid) ret += query1(lson, x, y);
if (mid < y) ret += query1(rson, x, y);
return ret;
}
segtree merge(segtree a, segtree b) {
segtree ret; ret.l = a.l; ret.r = b.r;
ret.tot = a.tot + b.tot; ret.pre = a.pre; ret.suf = b.suf;
if (a.pre == a.r - a.l + 1) ret.pre += b.pre;
if (b.suf == b.r - b.l + 1) ret.suf += a.suf;
ret.mx = max(max(a.mx, b.mx), a.suf + b.pre);
return ret;
}
segtree query2(int ind, int x, int y) {
int l = tr[ind].l, r = tr[ind].r;
if (x <= l && r <= y) return tr[ind];
int mid = (l + r) >> 1; segtree a, b; a.mx = b.mx = -1;
pushdown(ind);
if (x <= mid) a = query2(lson, x, y);
if (mid < y) b = query2(rson, x, y);
if (a.mx == -1) return b;
else if (b.mx == -1) return a;
else return merge(a, b);
}
int main() {
n = read(); m = read();
build(1, 1, n);
for (int i = 1; i <= m; i++) {
tp = read();
if (tp == 0) {
l0 = read(); r0 = read();
update1(1, l0, r0);
} else if (tp == 1) {
l0 = read(); r0 = read(); l1 = read(); r1 = read();
int num = query1(1, l0, r0); update1(1, l0, r0); update2(1, l1, r1, num);
} else {
l0 = read(); r0 = read();
segtree ans = query2(1, l0, r0);
printf("%d
", ans.mx);
}
}
return 0;
}