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;
}
分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

7 条评论

Sagacity · 2020年3月2日 5:48 下午

嗯嗯好的,这个我现在明白了,但是您方便帮我看一眼我之前写的这个代码,思路和你差不多,但是怎么也过不去行吗?实在打扰了,代码链接:https://paste.ubuntu.com/p/vrspr7rBkH/

    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;

Sagacity · 2020年2月29日 8:23 下午

为什么查询那里 return 前还需要更新一下 res 呐?

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

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

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注