题目描述

难度分:$2400$

输入$n(1 \leq n \leq 10^6)$，$m(1 \leq m \leq 3 \times 10^5)$和长为$n$的字符串$s$，只包含$4$和$7$，下标从$1$开始。

然后输入$m$个操作，有两种：

• switch l r：翻转$s[l]$到$s[r]$，也就是把这段子串的$4$变成$7$，$7$变成$4$。
• count：输出$s$的最长非降子序列的长度。

输入样例$1$

2 3
47
count
switch 1 2
count

输出样例$1$

2
1

输入样例$2$

3 5
747
count
switch 1 1
count
switch 1 3
count

输出样例$2$

2
3
2

算法

线段树

设一个区间$[l,r]$内$4$的数量是$c_4$，$7$的数量是$c_7$，最长非降子序列长度为$c_{47}$，最长非升子序列长度为$c_{74}$。则在合并$u$的两个孩子节点$l$和$r$时，规则如下：

1. $u.c_4$和$u.c_7$都是直接把左右孩子的对应属性相加。
2. $u.c_{47}=max(l.c_{47}+r.c_7,l.c_4+r.c_{47})$，左边$4$的数量接上右边最长非降序列的长度，或者左边最长非降序列的长度接上右边$7$的数量。
3. $u.c_{74}=max(l.c_{74}+r.c_4,l.c_7+r.c_{74})$，左边最长非升序列的长度接上右边$4$的数量，或者左边$7$的数量接上右边最长非升序列的长度。

当进行翻转操作时，交换节点的$c_4$和$c_7$两个属性，$c_{47}$和$c_{74}$两个属性即可。

复杂度分析

时间复杂度

构建线段树的时间复杂度为$O(nlog_2n)$。$m$个询问每个询问都要对线段树进行修改或查询操作，时间复杂度为$O(mlog_2n)$。因此，整个算法的时间复杂度为$O((n+m)log_2n)$。

空间复杂度

空间瓶颈在于线段树，因此额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;

const int N = 1000010;
int n, m, l, r;
char s[N], op[10];

class SegmentTree {
public:
    int arr[N];      // 初始数组
    struct Tag {
        int add;
        Tag() {
            add = 0;
        }
    };
    struct Info {
        int l, r, c4, c7, c47, c74;
        Tag lazy;
        Info() {}
        Info(int left, int right, int val): l(left), r(right) {
            if(val == 4) {
                c4 = 1, c7 = 0;
                c47 = c74 = 1;
            }else {
                c4 = 0, c7 = 1;
                c47 = c74 = 1;
            }
        }
    } tr[N<<2];

    explicit SegmentTree() {}

    void build(int u, int l, int r) {
        if(l == r) {
            tr[u] = Info(l, r, arr[l]);
        }else {
            int mid = (l + r) >> 1;
            build(lc(u), l, mid);
            build(rc(u), mid + 1, r);
            pushup(u);
        }
    }

    void modify(int l, int r) {
        modify(1, l, r);
    }

    Info query(int l, int r) {
        return query(1, l, r);
    }

private:
    int lc(int u) { 
        return u<<1;
    }

    int rc(int u) {
        return u<<1|1;
    }

    void pushup(int u) {
        tr[u] = merge(tr[lc(u)], tr[rc(u)]);
    }

    void pushdown(int u) {
        if(not_null(tr[u].lazy)) {
            down(u);
            clear_lazy(tr[u].lazy);      // 标记下传后要清空
        }
    }

    void modify(int u, int l, int r) {
        if(l <= tr[u].l && tr[u].r <= r) {
            swap(tr[u].c4, tr[u].c7);
            swap(tr[u].c47, tr[u].c74);
            tr[u].lazy.add ^= 1;
            return;
        }
        pushdown(u);
        int mid = (tr[u].l + tr[u].r) >> 1;
        if(r <= mid) {
            modify(lc(u), l, r);       // 区间在左子树
        }else if(l > mid) {
            modify(rc(u), l, r);       // 区间在右子树
        }else {
            // 区间横跨左右子树
            modify(lc(u), l, mid);
            modify(rc(u), mid + 1, r);
        }
        pushup(u);
    }

    Info query(int u, int l, int r) {
        if(l <= tr[u].l && tr[u].r <= r) return tr[u];
        pushdown(u);
        int mid = (tr[u].l + tr[u].r) >> 1;
        if(r <= mid) {
            return query(u<<1, l, r);
        }else if(mid < l) {
            return query(u<<1|1, l, r);
        }else {
            return merge(query(u<<1, l, r), query(u<<1|1, l, r));
        }
    }

    Info merge(const Info& lchild, const Info& rchild) {
        Info info;
        info.l = lchild.l, info.r = rchild.r;
        info.c4 = lchild.c4 + rchild.c4;
        info.c7 = lchild.c7 + rchild.c7;
        info.c47 = max(lchild.c4 + rchild.c47, lchild.c47 + rchild.c7);
        info.c74 = max(lchild.c7 + rchild.c74, lchild.c74 + rchild.c4);
        return info;
    }

    // 下传标记的规则
    void down(int u) {
        auto &lson = tr[lc(u)], &rson = tr[rc(u)];
        lson.lazy.add ^= 1, rson.lazy.add ^= 1;
        swap(lson.c4, lson.c7);
        swap(lson.c47, lson.c74);
        swap(rson.c4, rson.c7);
        swap(rson.c47, rson.c74);
    }

    // 判断标记是否为空的规则
    bool not_null(Tag& lazy) {
        return lazy.add != 0;
    }

    // 清空标记的规则
    void clear_lazy(Tag& lazy) {
        lazy.add = 0;
    }
};

int main() {
    scanf("%d%d", &n, &m);
    scanf("%s", s + 1);
    SegmentTree seg;
    for(int i = 1; i <= n; i++) {
        seg.arr[i] = s[i] - '0';
    }
    seg.build(1, 1, n);
    for(int i = 1; i <= m; i++) {
        scanf("%s", op);
        if(op[0] == 's') {
            scanf("%d%d", &l, &r);
            seg.modify(l, r);
        }else {
            auto info = seg.query(1, n);
            printf("%d\n", info.c47);
        }
    }
    return 0;
}