# 2. 题解

• 从左端开始的最长连续 1 的个数
• 从左端开始的最长连续 0 的个数
• 从右端开始的最长连续 1 的个数
• 从右端开始的最长连续 0 的个数
• 区间内最长连续的 1 的个数
• 区间内最长连续的 0 的个数

#include <bits/stdc++.h>

#define LS(a) (a << 1)
#define RS(a) (a << 1 | 1)
#define NS (100005)

using namespace std;

template <typename _Tp> inline void IN(_Tp& dig)
{
char c; bool flag = 0; dig = 0;
while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
if (flag) dig = -dig;
}

struct N {int l1, r1, m1, l0, r0, m0, tag;} e[NS << 2];

int n, m, arr[NS];

void Swp(int a)
{
swap(e[a].l1, e[a].l0);
swap(e[a].r1, e[a].r0);
swap(e[a].m1, e[a].m0);
}

void pup(int a)
{
int l = LS(a), r = RS(a);
if (!e[l].m0) e[a].l1 = e[l].l1 + e[r].l1;
else e[a].l1 = e[l].l1;
if (!e[r].m0) e[a].r1 = e[r].r1 + e[l].r1;
else e[a].r1 = e[r].r1;
if (!e[l].m1) e[a].l0 = e[l].l0 + e[r].l0;
else e[a].l0 = e[l].l0;
if (!e[r].m1) e[a].r0 = e[r].r0 + e[l].r0;
else e[a].r0 = e[r].r0;
e[a].m0 = max(e[l].r0 + e[r].l0, max(e[l].m0, e[r].m0));
e[a].m1 = max(e[l].r1 + e[r].l1, max(e[l].m1, e[r].m1));
}

void pdown(int a)
{
if (!e[a].tag) return;
Swp(LS(a)), Swp(RS(a));
e[LS(a)].tag ^= 1, e[RS(a)].tag ^=1, e[a].tag = 0;
}

void Build(int L = 1, int R = n, int a = 1)
{
memset(&e[a], 0, sizeof(N));
if (L == R)
{
if (arr[L]) e[a].l1 = e[a].r1 = e[a].m1 = 1;
else e[a].l0 = e[a].r0 = e[a].m0 = 1;
return;
}
int Mid = (L + R) >> 1;
Build(L, Mid, LS(a)), Build(Mid + 1, R, RS(a)), pup(a);
}

void Rev(int l, int r, int L = 1, int R = n, int a = 1)
{
if (l <= L && R <= r) {Swp(a), e[a].tag ^= 1; return;}
pdown(a); int Mid = (L + R) >> 1;
if (l <= Mid) Rev(l, r, L, Mid, LS(a));
if (r > Mid) Rev(l, r, Mid + 1, R, RS(a));
pup(a);
}

int Query(int l, int r, int L = 1, int R = n, int a = 1)
{
if (l <= L && R <= r) return e[a].m1;
pdown(a); int Mid = (L + R) >> 1, res = 0;
if (l <= Mid) res = max(res, Query(l, r, L, Mid, LS(a)));
if (r > Mid) res = max(res, Query(l, r, Mid + 1, R, RS(a)));
res = max(res, min(Mid - l + 1, e[LS(a)].r1) + min(r - Mid, e[RS(a)].l1));
return res;
}

int main(int argc, char const* argv[])
{
while (~scanf("%d", &n))
{
for (int i = 1; i <= n; i += 1) IN(arr[i]);
Build(), IN(m);
for (int c = 1, o, l, r; c <= m; c += 1)
{
IN(o), IN(l), IN(r);
if (o) Rev(l, r);
else printf("%d\n", Query(l, r));
}
}
return 0;
}

### 7 条评论

#### Remmina · 2020年3月2日 7:45 下午

你确定要一个退役快一年的弱智选手帮您看代码嘛？

好吧我看看。。。

#### Sagacity · 2020年3月2日 8:20 下午

实在感谢大佬，我那天改五个小时真的改吐了都要，真的十分感谢！

#### Remmina · 2020年3月2日 8:42 下午

QAQ 不谢啦，退役 OIer 还能看得懂代码已经让我倍感欣慰了

#### Remmina · 2020年3月2日 8:14 下午

改好了，你需要在 build 里清空 lazy 标记
即在代码第 45 行插入：lazy[rt]=0;

#### Remmina · 2020年3月1日 11:43 上午

额，就是分治呀。
先递归查了左右子区间的最长长度，然后用 “横跨了 Mid 的最长长度” 来更新一下 res。
因为递归查到的答案是局限在左右子区间内的，也就是更新前 res 一定小于等于子区间长度
而横跨了 Mid 的最长长度是可能大于子区间长度的（最长是两个子区间长度）
不知道表述清楚没有，若还有疑问欢迎提出 QAQ