题目描述

难度分:$2400$

输入$n(1 \leq n \leq 10^5)$，$q(1 \leq q \leq 10^5)$和长为$n$的字符串$s$，只包含a,b,c。

然后输入$q$个操作，每个操作输入$i(1 \leq i \leq n)$和$c(c$是a或者b或者c)。

每个操作会把$s[i]$改成$c$。每次操作后，要使$s$不包含子序列abc，至少要删除多少个字母？

注：子序列不一定连续。

输入样例

9 12
aaabccccc
4 a
4 b
2 b
5 a
1 b
6 b
5 c
2 a
1 a
5 a
6 b
7 b

输出样例

0
1
2
2
1
2
1
2
2
2
2
2

算法

线段树优化DP

如果是个静态的字符串，这个题的DP思路是比较好想的，但这个字符串可以动态改变所以需要数据结构加以优化。

状态定义

线段树每个节点所管辖的区间范围内，维护以下$6$个信息：

1. 消除所有a需要操作的最少次数$a$。
2. 消除所有b需要操作的最少次数$b$。
3. 消除所有c需要操作的最少次数$c$。
4. 消除所有ab需要操作的最少次数$ab$。
5. 消除所有bc需要操作的最少次数$bc$。
6. 消除所有abc需要操作的最少次数$abc$。

状态转移

每当修改字符串的一个字符$s[i]=c$，就更新线段树根所有节点的$6$个信息，最终答案就是根节点的$abc$值。

对于某个节点（假设这个节点管辖区间为$[l,r]$）的左右两个子节点$lchild$、$rchild$，如果两个区间的信息要合并，状态转移如下：

1. 要消除$[l,r]$内部的所有a，就把左右两个子区间的a都消除，状态转移方程为$lchild.a+rchild.a$。
2. 要消除$[l,r]$内部的所有b，就把左右两个子区间的b都消除，状态转移方程为$lchild.b+rchild.b$。
3. 要消除$[l,r]$内部的所有c，就把左右两个子区间的c都消除，状态转移方程为$lchild.c+rchild.c$。
4. 要消除$[l,r]$内部的所有ab，有两种方式：把左区间的a消除+把右区间的ab消除；把左区间的ab消除+把右区间的b消除。两种策略选较小值转移，状态转移方程为$min(lchild.a+rchild.ab,lchild.ab+rchild.b)$。
5. 要消除$[l,r]$内部的所有bc，有两种方式：把左区间的b消除+把右区间的bc消除；把左区间的bc消除+把右区间的c消除。两种策略选较小值转移，状态转移方程为$min(lchild.b+rchild.bc,lchild.bc+rchild.c)$。
6. 要消除$[l,r]$内部的所有abc，有三种方式：把左区间的a消除+把右区间的abc消除；把左区间的abc消除+把右区间的c消除；把左区间的ab消除+把右区间的bc消除。三种策略选较小值转移，状态转移方程为$min(lchild.a+rchild.abc, lchild.abc+rchild.c, lchild.ab+rchild.bc)$。

复杂度分析

时间复杂度

线段树初始化的时间复杂度为$O(nlog_2n)$。$q$次询问，每次状态转移就是线段树进行单点修改的时间复杂度，$q$条询问的总时间复杂度为$O(qlog_2n)$。因此，整个算法的时间复杂度为$O((n+q)log_2n)$。

空间复杂度

线段树的空间复杂度为$O(n)$，每次状态转移需要递归，递归深度是$O(log_2n)$，为状态转移时的空间复杂度。所以空间瓶颈就是线段树的空间消耗，整个算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 100010;
int n, q;
char s[N];

class SegmentTree {
public:
    struct Info {
        int l, r;
        LL a, b, c, ab, bc, abc;
        Info() {}
        Info(int left, int right, LL val) {
            l = left;
            r = right;
            a = b = c = ab = bc = abc = 0;
            if(val == 0) a = 1;
            if(val == 1) b = 1;
            if(val == 2) c = 1;
        }
    } seg[N<<2];

    explicit SegmentTree() {}

    void build(int u, int l, int r) {
        if(l == r) {
            seg[u] = Info(l, r, s[r] - 'a');
        }else {
            int mid = l + r >> 1;
            build(u<<1, l, mid);
            build(u<<1|1, mid + 1, r);
            pushup(u);
        }
    }

    void modify(int pos, LL val) {
        modify(1, pos, val);
    }

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

private:
    void modify(int u, int pos, LL val) {
        if(seg[u].l == pos && seg[u].r == pos) {
            seg[u] = Info(pos, pos, val);
        }else {
            int mid = seg[u].l + seg[u].r >> 1;
            if(pos <= mid) {
                modify(u<<1, pos, val);
            }else {
                modify(u<<1|1, pos, val);
            }
            pushup(u);
        }
    }

    Info query(int u, int l, int r) {
        if(l <= seg[u].l && seg[u].r <= r) {
            return seg[u];
        }
        int mid = seg[u].l + seg[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));
        }
    }

    void pushup(int u) {
        seg[u] = merge(seg[u<<1], seg[u<<1|1]);
    }

    Info merge(const Info& lchild, const Info& rchild) {
        Info info;
        info.l = lchild.l;
        info.r = rchild.r;
        info.a = lchild.a + rchild.a;
        info.b = lchild.b + rchild.b;
        info.c = lchild.c + rchild.c;
        info.ab = min(lchild.a + rchild.ab, lchild.ab + rchild.b);
        info.bc = min(lchild.b + rchild.bc, lchild.bc + rchild.c);
        info.abc = min({lchild.a + rchild.abc, lchild.ab + rchild.bc, lchild.abc + rchild.c});
        return info;
    }
};

int main() {
    scanf("%d%d", &n, &q);
    scanf("%s", s + 1);
    SegmentTree seg;
    seg.build(1, 1, n);
    int pos;
    char c;
    for(int i = 1; i <= q; i++) {
        cin >> pos >> c;
        seg.modify(pos, c - 'a');
        printf("%lld\n", seg.query(1, n).abc);
    }
    return 0;
}