1. 题目

传送门=￣ω￣=

题意：

就是给你一段由 0 和 1 组成的序列，然后有两种操作：0 a b 就是问从 a 到 b 最长的连续的 1 的长度为多少，1 a b 就是把从 a 到 b 的数据是一的更新为 0，是零的更新为 1。

数据范围是 $10^5$

2. 题解

嗯。。。运用一下分治的思想就行啦～

搞个线段树，每个节点记录对应区间的：

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

根据分治的思想合并左右子区间的信息得到当前区间信息就行啦！

具体看代码吧，还是比较清晰的 QvQ

代码：

#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;
}